GSS2 - Can you answer these queries II
Being a completist and a simplist, kid Yang Zhe cannot solve but
get Wrong Answer from most of the OI problems. And he refuse to
write two program of same kind at all. So he always failes in
contests.
When having a contest, Yang Zhe looks at the score of every
problems first. For the problems of the same score, Yang Zhe will
do only one of them. If he's lucky enough, he can get all the scores
wanted.
Amber is going to hold a contest in SPOJ. She has made a list of
N candidate problems, which fit Yang Zhe very well. So Yang
Zhe can solve any problem he want. Amber lined up the problems,
began to select. She will select a subsequence of the list as the
final problems. Being A girl of great compassion, she'd like to
select such a subsequence (can be empty) that Yang Zhe will get the
maximal score over all the possible subsequences.
Amber found the subsequence easily after a few minutes. To make
things harder, Amber decided that, Yang Zhe can take this contest
only if Yang Zhe can answer her Q questions. The question is:
if the final problems are limited to be a subsequence
of list[X..Y] (1 <= X <= Y <= N),
what's the maximal possible score Yang Zhe can get?
As we know, Yang Zhe is a bit idiot (so why did he solve the
problem with a negative score?), he got Wrong Answer again... Tell
him the correct answer!
Input
- Line 1: integer N (1 <= N <= 100000);
- Line 2: N integers denoting the score of each problem,
each of them is a integer in range [-100000, 100000]; - Line 3: integer Q (1 <= Q <= 100000);
- Line 3+i (1 <= i <= Q): two
integers X and
Y denoting the ith question.
Output
- Line i: a single integer, the answer to the ith
question.
Example
Input:
9
4 -2 -2 3 -1 -4 2 2 -6
3
1 2
1 5
4 9 Output:
4
5
3
Warning: large input/output data,be careful with certain languages
给出A[1],A[2]...,A[N], 有Q次询问，每次询问包含x,y,
需要回答Max{a[i]+a[i+1]+...+a[j]; x <= i <= j <= y}，相同的数只能计算一次。
看到题目还以为是DP，根本没往线段树上想，看了题解感觉好神奇啊。。。
先将查询区间离线并且排序（类似莫队算法），然后循环 i =1~n，对于每一个a[i]，插入进线段树更新节点。而线段树的每一个节点维护四个数组。sum[rt]表示以a[i]结尾的
最大的后缀和，presum[rt]表示1,~n中最大的区间和（a[j]+...+a[k],1<=j<=k<=i），lazy[rt]为懒惰标记，做过区间修改的应该知道，prelazy[rt]则为此区间最大的lazy。
然后就是线段树的事了。代码不难，应该很好理解，虽然我花了两天才看懂=_=
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
typedef long long ll;
const int N=2e5+;
const int M=N*N+;
ll a[N];
ll num,m,n,tot=;
ll sum[N*],presum[N*],ans[N];
ll lazy[N*],prelazy[N*],pre[N*];
struct man{
ll l,r,id;
bool operator < (const man & b) const {
return r < b.r;
}
}q[N];
void Push_down(int rt) {
if(lazy[rt]||prelazy[rt]) {
presum[rt*]=max(presum[rt*],sum[rt*]+prelazy[rt]);
prelazy[rt*]=max(prelazy[rt*],lazy[rt*]+prelazy[rt]);
sum[rt*]+=lazy[rt];lazy[rt*]+=lazy[rt]; presum[rt*+]=max(presum[rt*+],sum[rt*+]+prelazy[rt]);
prelazy[rt*+]=max(prelazy[rt*+],lazy[rt*+]+prelazy[rt]);
sum[rt*+]+=lazy[rt];lazy[rt*+]+=lazy[rt];
lazy[rt]=prelazy[rt]=;
}
}
void Push_up(ll rt){
presum[rt]=max(presum[rt*],presum[rt*+]);
sum[rt]=max(sum[rt*],sum[*rt+]);
}
void Update(ll L,ll R,ll l,ll r,ll rt,ll add) {
if(l>=L&&r<=R) {
lazy[rt]+=add;
sum[rt]+=add;
prelazy[rt]=max(prelazy[rt],lazy[rt]);
presum[rt]=max(presum[rt],sum[rt]);
return;
}
Push_down(rt);
ll m=(r+l)>>;
if(L<=m)Update(L,R,lson,add);
if(R>m) Update(L,R,rson,add);
Push_up(rt);
}
ll Query(ll L,ll R,ll l,ll r,ll rt) {
if(L<=l&&r<=R)return presum[rt];
Push_down(rt);
ll m=(l+r)>>,ans=-;
if(L<=m)ans=max(ans,Query(L,R,lson));
if(R>m)ans=max(ans,Query(L,R,rson));
return ans;
} int main() {
scanf("%lld",&n);
for(int i=;i<=n;i++){
scanf("%lld",&a[i]);
}
scanf("%lld",&m);
for(int i=;i<m;i++){
scanf("%lld%lld",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q,q+m);
ll cnt=;
for(int i=;i<=n;i++){
Update(pre[a[i]+N]+,i,,n,,a[i]);
pre[a[i]+N]=i;
while(cnt<m&&q[cnt].r==i){
ans[q[cnt].id]=Query(q[cnt].l,q[cnt].r,,n,);
cnt++;
}
}
for(int i=;i<m;i++)printf("%lld ",ans[i]);printf("\n");
return ;
}