【BZOJ2482】[Spoj1557] Can you answer these queries II
Description
给定n个元素的序列。
给出m个询问：求l[i]~r[i]的最大子段和（可选空子段）。
这个最大子段和有点特殊：一个数字在一段中出现了两次只算一次。
比如：1，2，3，2，2，2出现了3次，但只算一次，于是这个序列的和是1+2+3=6。
Input
第一行一个数n。
第二行n个数，为给定的序列，这些数的绝对值小于等于100000。
第三行一个数m。
接下来m行，每行两个数，l[i]，r[i]。
Output
M行，每行一个数，为每个询问的答案。
Sample Input
9
4 -2 -2 3 -1 -4 2 2 -6
3
1 2
1 5
4 9
4 -2 -2 3 -1 -4 2 2 -6
3
1 2
1 5
4 9
Sample Output
4
5
3
5
3
HINT
【数据说明】
30%：1 <= n, m <= 100
100%：1 <= n, m <= 100000
题解：还是考虑这点：每个子串都是某个前缀的后缀，所以我们依旧枚举每个前缀，用线段树维护它的所有后缀。
出现两次只算一次怎么办？只需要在扫到一个数的时候将它上一个出现的位置变成0即可，这样就会改边很多后缀的值，用线段树去维护。
但是本题求的是最大连续子段和啊，其实只需要维护每个后缀的历史最大值就可以了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lson x<<1
#define rson x<<1|1
using namespace std;
const int maxn=100010;
typedef long long ll;
int n,m;
int last[maxn<<1],pre[maxn],v[maxn];
ll ans[maxn];
struct node
{
ll t,ht,s,hs;
}s[maxn<<2];
struct QUERY
{
int l,r,org;
}q[maxn];
inline void phd(int x,int y)
{
if(y>0) s[x].hs=max(s[x].hs,s[x].s+y),s[x].ht=max(s[x].ht,s[x].t+y);
}
inline void pd(int x,int y)
{
s[x].s+=y,s[x].t+=y;
if(y>0) s[x].hs=max(s[x].hs,s[x].s),s[x].ht=max(s[x].ht,s[x].t);
}
inline void pushdown(int x)
{
if(s[x].ht) phd(lson,s[x].ht),phd(rson,s[x].ht),s[x].ht=0;
if(s[x].t) pd(lson,s[x].t),pd(rson,s[x].t),s[x].t=0;
}
inline void pushup(int x)
{
s[x].s=max(s[lson].s,s[rson].s),s[x].hs=max(s[lson].hs,s[rson].hs);
}
void updata(int l,int r,int x,int a,int b,int c)
{
if(a<=l&&r<=b)
{
pd(x,c);
return ;
}
pushdown(x);
int mid=(l+r)>>1;
if(a<=mid) updata(l,mid,lson,a,b,c);
if(b>mid) updata(mid+1,r,rson,a,b,c);
pushup(x);
}
ll query(int l,int r,int x,int a,int b)
{
if(a<=l&&r<=b) return s[x].hs;
pushdown(x);
int mid=(l+r)>>1;
if(b<=mid) return query(l,mid,lson,a,b);
if(a>mid) return query(mid+1,r,rson,a,b);
return max(query(l,mid,lson,a,b),query(mid+1,r,rson,a,b));
}
bool cmp(const QUERY &a,const QUERY &b)
{
return a.r<b.r;
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
n=rd();
int i,j;
for(i=1;i<=n;i++) v[i]=rd(),pre[i]=last[v[i]+100000],last[v[i]+100000]=i;
m=rd();
for(i=1;i<=m;i++) q[i].l=rd(),q[i].r=rd(),q[i].org=i;
sort(q+1,q+m+1,cmp);
for(i=j=1;i<=n;i++)
{
updata(1,n,1,pre[i]+1,i,v[i]);
for(;q[j].r==i;j++) ans[q[j].org]=query(1,n,1,q[j].l,i);
}
for(i=1;i<=m;i++) printf("%lld
",ans[i]);
return 0;
}