题目大意：
给一个 \(n\) 个元素的序列，\(q\) 次询问 \([l_i,r_i]\) 的最大子段和（相同元素只算一个）。
\(n,q \le 10^5,- 10^5\le a_i \le 10^5\).
解法：
首先考虑最大子段和的经典动态解法：维护 \(pre_i,suf_i,sum_i,mxsum_i\) 。这个时候你会发现无法合并。
Tips:对于区间询问问题，在没有思路时将其离线是一个很好的选择。
考虑离线问题并按右端点为第一关键字，右端点为第二关键字排序。用一个指针在数组中从左到右滑动，并同时加入滑动到的新点。
那么加入一个新点的具体操作是什么呢？
我们考虑一个指针指向的元素为 \(j\)，那么加入 \(j\) 可能会对哪些区间 \([i,j]\) 产生贡献呢？
显然是 \([lst_j+1,j]\)（\(lst_j\) 表示左边最后一个与 \(a_j\) 相等的下标）。
联想到我们对一个静态序列求最大子段和的贪心算法，这个加点操作可以转化为在一些序列中加入一个新的元素，并同时更新这些序列的最大子段和，最后取所有序列中最大值为答案。
具体来说：
对于每个左端点 \(i\) ，如果 \(i\) 与可能与它连接并产生贡献的点连接成为一个序列，那么第 \(k\) 个询问答案实际上就是以 \([l_i,r_i]\) 中所有每个点开头组成的序列的最大子段和的最大值。
那么我们用一颗线段树来维护这些信息即可。
此时每个序列的最大子段和其实就是更新时的区间和的历史最大值。
code:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,INF=1e9+7;
int n,m,a[N],lst[N],ans[N];
map<int,int>ptr;
struct Segment_tree{
#define ls (o<<1)
#define rs (o<<1|1)
#define mid ((l+r)>>1)
int tmx[N<<2],tsum[N<<2],htag[N<<2],stag[N<<2];
void pushup(int o){
tsum[o]=max(tsum[ls],tsum[rs]);
tmx[o]=max(tmx[ls],tmx[rs]);
}
void pushdown(int o){
tmx[ls]=max(tmx[ls],tsum[ls]+htag[o]);tmx[rs]=max(tmx[rs],tsum[rs]+htag[o]);
tsum[ls]+=stag[o];tsum[rs]+=stag[o];
htag[ls]=max(htag[ls],stag[ls]+htag[o]);htag[rs]=max(htag[rs],stag[rs]+htag[o]);
stag[ls]+=stag[o];stag[rs]+=stag[o];
stag[o]=htag[o]=0;
}
void add(int o,int l,int r,int s,int t,int k){
if(s<=l&&r<=t){
tsum[o]+=k;tmx[o]=max(tmx[o],tsum[o]);
stag[o]+=k;
htag[o]=max(htag[o],stag[o]);
return;
}
pushdown(o);
if(s<=mid)add(ls,l,mid,s,t,k);
if(mid<t)add(rs,mid+1,r,s,t,k);
pushup(o);
return;
}
int querytmax(int o,int l,int r,int s,int t){
if(s<=l&&r<=t)return tmx[o];
int ret=-INF;
pushdown(o);
if(s<=mid)ret=querytmax(ls,l,mid,s,t);
if(mid<t)ret=max(ret,querytmax(rs,mid+1,r,s,t));
return ret;
}
}tree;
struct query{
int l,r;
int id;
}q[N];
bool cmp(struct query q1,struct query q2){
if(q1.r!=q2.r)return q1.r<q2.r;
return q1.l<q2.l;
}
signed main(){
std::ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
lst[i]=ptr[a[i]];
ptr[a[i]]=i;
}
cin>>m;
for(int i=1;i<=m;i++)cin>>q[i].l>>q[i].r,q[i].id=i;
sort(q+1,q+m+1,cmp);
for(int i=1;i<=m;i++){
for(int j=q[i-1].r+1;j<=q[i].r;j++)tree.add(1,1,n,lst[j]+1,j,a[j]);
ans[q[i].id]=tree.querytmax(1,1,n,q[i].l,q[i].r);
}
for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
return 0;
}