GSS2 - Can you answer these queries II

GSS2 - Can you answer these queries II

题意：
给你$1e5$ 的序列，每次询问区间$l到r$，每个相同的数只算一次的最大子段和。

思路：
乍一眼看上去，是不是没有头绪。
对于这种数据结构题，如果在线维护很麻烦的话，可以想想离线的做法！
将所有区间离线下来，并按照 $r$ 升序排序。那么就可以一个个地加数，考虑维护 一个值$DP[l]$ 即以$l$为左端点到 当前位置的 最大子段和，可以发现，不断地往里面加数字，那么最大字段和，其实就是 —— 历史最大值！
因为每个相同的数字只能算一次，所以只需要在上一次出现的位置+1 ，到当前位置加 即可。

自言自语：多想想离线做法！离线可能就换了一道题了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int qread(){
    int s=0,w=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;for (;ch>='0'&&ch<='9';ch=getchar())s=(s<<1)+(s<<3)+(ch^48);return (w==-1?-s:s);}const int INF=2e9;
int n,m;
int s[100050];
ll ans[100050];
struct no{
    int id,l; 
};
int pos[100050];
int nex[100050];
vector<no>v[100050];
struct node{
    ll mx_,add_,mx,add;
}tr[400050];
#define ls p<<1
#define rs p<<1|1
#define mid (l+r>>1)
void pushup(int p){
    tr[p].mx=max(tr[ls].mx,tr[rs].mx);tr[p].mx_=max(tr[ls].mx_,tr[rs].mx_);
}
void plu(int p,int k1,int k2){
    tr[p].mx_=max(tr[p].mx_,tr[p].mx+k2);tr[p].mx+=k1;tr[p].add_=max(tr[p].add_,tr[p].add+k2);tr[p].add+=k1;
}
void pushdown(int p){
    if(tr[p].add){
    plu(ls,tr[p].add,tr[p].add_);plu(rs,tr[p].add,tr[p].add_);tr[p].add=tr[p].add_=0;}
}
void build(int p,int l,int r){
    tr[p].add=tr[p].add_=0;if(l==r){
    tr[p].mx=tr[p].mx_=0;return;}build(ls,l,mid);build(rs,mid+1,r);pushup(p);
}
void update(int p,int l,int r,int x,int y,int w){
    if(x<=l&&r<=y){
    plu(p,w,w);return;}pushdown(p); if(x<=mid)update(ls,l,mid,x,y,w);if(mid<y)update(rs,mid+1,r,x,y,w);pushup(p);
}
ll query(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y)return tr[p].mx_;pushdown(p);ll ans=-1e15;if(x<=mid)ans=max(ans,query(ls,l,mid,x,y));if(mid<y)ans=max(ans,query(rs,mid+1,r,x,y));return ans;
}
#undef ls
#undef rs
#undef mid 
int main(){
    n=qread();for(int i=1;i<=n;i++){
    s[i]=qread();nex[i]=pos[s[i]];pos[s[i]]=i;}m=qread();for(int i=1;i<=m;i++){
    int a=qread(),b=qread();v[b].push_back({
    i,a});}build(1,1,n);for(int i=1;i<=n;i++){
    update(1,1,n,nex[i]+1,i,s[i]);for(auto to:v[i]){
    ans[to.id]=query(1,1,n,to.l,i); }}for(int i=1;i<=m;i++)printf("%lld\n",ans[i]); return 0;
}