SP1557 GSS2 - Can you answer these queries II

线段树。

发现这道题很好将询问离线。。。那就离线呗。

按右端点排序，然后同一个右端点的在一个循环里面处理。

考虑到一段区间里面重复的只能算一次，从前往后记录跟 $i$ 位置数值相同的上一个位置 $pre[i]$ ，那 $pre[i]$ 前面的区间就不允许 $a[i]$ 产生贡献了。。。那只允许 $pre[i]+1$ 到 $i$ 的位置能够拥有这个贡献不久好了嘛。。。

维护四个 $tag$ ：

• $sum$ ，区间内所有数字的和
• $history\ sum$ ，从最开始到现在的 $sum$ 的最大值
• $lazytagsum$ ，$sum$ 的懒标记
• $lazytag\ history\ sum$ ，第二个的懒标记

其实就是开两个线段树一个储存现在的区间和的情况一个储存最大的区间和的情况。。。

核心就是维护这两个就行了吧。。。

最后计算的时候直接用这个区间的 $hsm$ 就好了。

至于为什么是左儿子和右儿子的 $hsm$ 取 $max$ 而不要考虑 $lhsm+rhsm$ 。。。最大子段和一定要是连续的啊如果最子段和刚好是中间那一段的话应该就会直接被返回 $tree[f].hm$ 吧。。。（如果真的这个区间是包含关系的话那应该在上层就起飞了

#include <bits/stdc++.h>
#define ll long long
#define maxn 400001
using namespace std;
ll n,q,pre[maxn<<1],num[maxn<<1],ans[maxn<<1];
ll a[maxn<<1];
ll m,j,ct;
struct Node{
    ll l,r,id;
}e[maxn];
struct NODE{
    ll sm=0,hm=0,lsm=0,lhm=0;
}tree[maxn];
//sum,historySum,lazytagsum,lazytag_hm

inline ll read(){
    ll x=0,f=0;char c=getchar();
    while(!isdigit(c))  f|=c=='-',c=getchar();
    while(isdigit(c))   x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}

inline int cmp(Node u,Node v){
    if(u.r==v.r)
        return u.l<v.l;
    return u.r<v.r;
}

inline void pushup(ll l,ll r,ll f){
    tree[f].sm=max(tree[f<<1].sm,tree[f<<1|1].sm);
    tree[f].hm=max(tree[f<<1].hm,tree[f<<1|1].hm);
}

inline void work(ll l,ll r,ll f,ll lsm,ll lhm){
    tree[f].hm=max(tree[f].hm,tree[f].hm+lhm);
    tree[f].sm+=lsm;
    tree[f].hm=max(tree[f].hm,tree[f].lsm+lhm);
    tree[f].lsm+=lsm;
}

inline void pushdown(ll l,ll r,ll f){
    ll mid=(l+r)>>1;
    work(l,mid,f<<1,tree[f].lsm,tree[f].lhm);
    work(mid+1,r,f<<1|1,tree[f].lsm,tree[f].lhm);
    tree[f].lsm=0;
    tree[f].lhm=0;
}

inline void add(ll l,ll r,ll f,ll cl,ll cr,ll x){
    if(cl<=l&&cr>=r){
        tree[f].sm+=x;
        tree[f].hm=max(tree[f].hm,tree[f].sm);
        tree[f].lsm+=x;
        tree[f].lhm=max(tree[f].lhm,tree[f].lsm);
        return;
    }
    ll mid=(l+r)>>1;
    pushdown(l,r,f);
    if(cl<=mid)     add(l,mid,f<<1,cl,cr,x);
    if(mid<cr)      add(mid+1,r,f<<1|1,cl,cr,x);
    pushup(l,r,f);  
}

inline ll query(ll l,ll r,ll f,ll cl,ll cr){
    if(cl<=l&&cr>=r)
        return tree[f].hm;
    ll mid=(l+r)>>1,val=-0x7f7f7f7f;
    pushdown(l,r,f);
    if(cl<=mid)     val=max(val,query(l,mid,f<<1,cl,cr));
    if(mid<cr)      val=max(val,query(mid+1,r,f<<1|1,cl,cr));
    return val;
}

int main(){
    n=read();
    for(register int i=1;i<=n;++i){
        a[i]=read();
        pre[i]=num[a[i]+maxn];
        num[a[i]+maxn]=i;
    }
    m=read();
    for(register int i=1;i<=m;++i){
        e[i].l=read();
        e[i].r=read();
        e[i].id=i;
    }
    sort(e+1,e+m+1,cmp);
    j=1;
    for(register int i=1;i<=n;++i){
        ll ql=pre[i]+1,qr=i,ct=a[i];
        add(1,n,1,ql,qr,ct);
        for(;e[j].r==i&&j<=m;++j)
            ans[e[j].id]=query(1,n,1,e[j].l,e[j].r);
    }
    for(register int i=1;i<=m;++i)
        printf("%lld\n",ans[i]);
    return 0;
}