题目解析
呐，是一道非常有意思的线段树的题呢（奇怪的语气
仅仅只是比GSS1多了一个去重的要求，思维方式就完全不一样了呢（更奇怪的语气
咳咳
像GSS1那样简单粗暴地维护(sum,mx,mxl,mxr)是无法处理“重复”这个限制的，我们需要用一种不同的方式来处理，我也是看了题解才知道怎么做，不过方法真的很妙！
我们把询问离线下来，按照右端点从小到大排。
然后遍历(1)到(n)，依次插入(a[i])，然后对每个(r==i)的询问进行处理。这么做的话，就达到了查询时，没有右端点右边的元素的效果。
首先，我们引入(A[j]=a[j]+a[j+1]+...+a[i])
即：
(A[1]=a[1]+a[2]+a[3]+...+a[i])
(A[2]=a[2]+a[3]+...+a[i])
(A[3]=a[3]+...+a[i])
...
(A[i]=a[i])
(A[i+1]=0)
关于插入
考虑插入一个新元素(a[i+1])，这时(i=i+1)
所以(A[j]=a[j]+a[j+1]+...+a[i]+a[i+1])
讲道理，我们应该把每一个(A[j])加上(a[i+1])，但是要去重，所以我们应该把不含(a[i+1])的所有(A[j])加上(a[i+1])
那么具体是哪些数呢？设(pre[a[i+1]])是上一次(a[i+1])出现的位置，那么在更新(pre[a[i+1]])那个位置的时候，我们就已经把所有的(pre[a[i+1]])以前的(A[j])都已经加了一次(a[i+1])了，它们不需要重复再加，所以应该把区间([pre[a[i+1]]+1,i+1])之间的数集体加(a[i+1])
小结：插入(a[i+1])时，把(A[pre[a[i+1]]+1])到(A[i+1])之间的所有数加(a[i+1])
容易发现这是一个区间加法，我们可以对(A[])建线段树维护。
关于查询
对于一个查询区间([l,r]，r==i)，我们在插入(a[i])之后进行查询。
如果枚举一个答案的左端点(j,j>=l)，发现由于(A[])中不含(r)右边的元素，所以任意一个(A[j])的右端点都在(r)以内，都是合法的，那么我们以(j)为区间左端点的产生的答案就是(A[j])出现过的历史最大值。我们要找([l,r])的答案，将枚举(j)产生的所有答案取最大值即可。
小结：查询([l,r]，r==i)，在插入(a[i])之后进行查询，枚举(j>=l)，答案是所有(A[j])的历史最大值的最大值。
那么在线段树上再维护一个历史最大和即可。
►Code View
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define LL long long
#define N 100005
#define DEL 100000
#define INF 0x3f3f3f3f
#define MOD 998244353
int rd()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48); c=getchar();}
return f*x;
}
int n,m,a[N],pre[N<<1],ans[N];
struct node{
int sum,hmx,stag,htag;
}tree[N<<2];
/*
叶节点
sum:对应的A[j]的值 即a[j]+a[j+1]+...+a[i]
hmx:sum的历史最大值
其它节点
sum:对应区间sum的最大值
hmx:对应区间hmx的最大值
stag和htag分别为对应的懒标记
stag是当前区间应该加多少
htag是从上一次下传标记到现在出现过的历史最大懒标记(即出现过的最大的往下面区间加多少的值
*/
struct queries{
int l,r,id;
}q[N];
bool cmp(queries x,queries y)
{
return x.r<y.r;
}
void PushUp(int i)
{
tree[i].sum=max(tree[i<<1].sum,tree[i<<1|1].sum);
tree[i].hmx=max(tree[i<<1].hmx,tree[i<<1|1].hmx);
tree[i].stag=tree[i].htag=0;
}
void PushDown(int i)
{
tree[i<<1].hmx=max(tree[i<<1].hmx,tree[i<<1].sum+tree[i].htag);
tree[i<<1].sum+=tree[i].stag;
tree[i<<1].htag=max(tree[i<<1].htag,tree[i<<1].stag+tree[i].htag);
tree[i<<1].stag+=tree[i].stag;
tree[i<<1|1].hmx=max(tree[i<<1|1].hmx,tree[i<<1|1].sum+tree[i].htag);
tree[i<<1|1].sum+=tree[i].stag;
tree[i<<1|1].htag=max(tree[i<<1|1].htag,tree[i<<1|1].stag+tree[i].htag);
tree[i<<1|1].stag+=tree[i].stag;
tree[i].stag=tree[i].htag=0;
}
void Update(int i,int l,int r,int ql,int qr,int val)
{
if(ql<=l&&r<=qr)
{
tree[i].sum+=val,tree[i].hmx=max(tree[i].hmx,tree[i].sum);
tree[i].stag+=val,tree[i].htag=max(tree[i].htag,tree[i].stag);
return ;
}
PushDown(i);
int mid=(l+r)>>1;
if(ql<=mid) Update(i<<1,l,mid,ql,qr,val);
if(qr>mid) Update(i<<1|1,mid+1,r,ql,qr,val);
PushUp(i);
return ;
}
node Query(int i,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)
return tree[i];
PushDown(i);
int mid=(l+r)>>1;
if(qr<=mid) return Query(i<<1,l,mid,ql,qr);
else if(ql>mid) return Query(i<<1|1,mid+1,r,ql,qr);
else
{
node x=Query(i<<1,l,mid,ql,qr),y=Query(i<<1|1,mid+1,r,ql,qr),res;
res.sum=max(x.sum,y.sum);
res.hmx=max(x.hmx,y.hmx);
res.htag=res.stag=0;
return res;
}
}
int main()
{
n=rd();
for(int i=1;i<=n;i++)
a[i]=rd();
m=rd();
for(int i=1;i<=m;i++)
q[i].l=rd(),q[i].r=rd(),q[i].id=i;
sort(q+1,q+m+1,cmp);
int j=1;
for(int i=1;i<=n;i++)
{
Update(1,1,n,pre[a[i]+DEL]+1,i,a[i]);
pre[a[i]+DEL]=i;
while(q[j].r==i&&j<=m)
ans[q[j].id]=Query(1,1,n,q[j].l,q[j].r).hmx,j++;
}
for(int i=1;i<=m;i++)
printf("%d
",ans[i]);
return 0;
}