题解 SP1557 【GSS2 - Can you answer these queries II】

· · 题解

\color{green}\Large\texttt{『菜鸡的blog』}

如果你觉得这篇题解还可以的话，也可以来看看我的其他博客qwq

此题与GSS1的区别在于选出的子段中，两个重复元素只算一次。

对于GSS1，我们的线段树做法一般是对每个节点维护区间最大子段、区间和、区间最大前缀、区间最大后缀。显然这种方式很难判断有无重复的元素，所以我们必须另寻别的方法。

我们先引入贡献这个东西

我们考虑对于每个l维护[l,i]的区间和A[l]+A[l+1]+...+A[i]去掉重复元素的影响之后的值。（i为最近一次插入的元素的位置，马上就会介绍）

这个称为l的贡献。

先别问这个东西有什么用……我们慢慢讲

如何保证重复元素只算入一次贡献

我们从前往后依次加元素，如果一个元素A[i]在前面的pre[A[i]]位置已经出现过了，那么就不让A[i]的加入对区间[\ 1,pre[A[i]]\ ]中元素的贡献产生影响。

那么如何让A[i]对[\ pre[A[i]]+1,i-1\ ]产生影响呢？

对于pre[A[i]]<l<i，我们都在l的原贡献序列A[l]+A[l+1]+...+A[i-1]后面接一个A[i]。

总结一下：其实我们是在进行区间加，把A[i]加到区间[\ pre[A[i]]+1,i-1\ ]上。

如何处理询问

对于询问(j,i)，我们就在刚刚加入A[i]之后查询\max(A[l]+A[l+1]+...+A[r])\quad(j\le l\le r\le i)。

注意到如果l固定，那么其实\max(A[l]+A[l+1]+...+A[r])\quad(l\le r\le i)就是l贡献的历史最大值。

（这样的r满足r\le i，所以肯定已经加入过了，A[l]+A[l+1]+...+A[r]就是当时l的贡献）。

总结一下：询问(j,i)就是在刚刚插入A[i]之后询问区间[\ j,i\ ]的历史贡献最大值。

可以加入线段树了

区间加，区间查询，显然这是线段树擅长的东西。

我们需要四个tag：

注意Query()的答案也要用类似push_up()的方式合并，所以建议写成结构体，push_up()我写成了重载的+。

push_down()细节较多，建议好好看一下。

然后是跑的慢死的代码。自我感觉上面已经讲得很清楚了所以就不注释了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int N,M;
int A[100005];
int pre[2000005];

struct node{
    ll Max,HisMax,Lzy,HisLzy;
    node operator +(const node b)const{
        node c;c.Max=max(Max,b.Max);c.HisMax=max(HisMax,b.HisMax);
        c.HisLzy=c.Lzy=0;
        return c;
    }
}K[400005];

void push_down(int x){
    K[x<<1].HisMax=max(K[x<<1].HisMax,K[x<<1].Max+K[x].HisLzy);
    K[x<<1].HisLzy=max(K[x<<1].HisLzy,K[x<<1].Lzy+K[x].HisLzy);
    K[x<<1].Max+=K[x].Lzy;
    K[x<<1].Lzy+=K[x].Lzy;
    K[x<<1|1].HisMax=max(K[x<<1|1].HisMax,K[x<<1|1].Max+K[x].HisLzy);
    K[x<<1|1].HisLzy=max(K[x<<1|1].HisLzy,K[x<<1|1].Lzy+K[x].HisLzy);
    K[x<<1|1].Max+=K[x].Lzy;
    K[x<<1|1].Lzy+=K[x].Lzy;

    K[x].Lzy=K[x].HisLzy=0;
}

void Update(int x,int l,int r,int L,int R,ll k){
    if(L<=l&&r<=R){
        K[x].Max+=k;K[x].HisMax=max(K[x].HisMax,K[x].Max);
        K[x].Lzy+=k;K[x].HisLzy=max(K[x].HisLzy,K[x].Lzy);
        return;
    }
    push_down(x);
    int mid=(l+r)>>1;
    if(L<=mid) Update(x<<1,l,mid,L,R,k);
    if(R>mid) Update(x<<1|1,mid+1,r,L,R,k);
    K[x]=K[x<<1]+K[x<<1|1];
    return;
}

node Query(int x,int l,int r,int L,int R){
    if(L<=l&&r<=R) return K[x];
    push_down(x);
    int mid=(l+r)>>1;
    if(R<=mid) return Query(x<<1,l,mid,L,R);
    if(L>mid) return Query(x<<1|1,mid+1,r,L,R);
    return Query(x<<1,l,mid,L,R)+Query(x<<1|1,mid+1,r,L,R);
}

int L[100005],R[100005],id[100005];
node Ans[100005];
bool cmp(int a,int b){
    return R[a]<R[b];
}

int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&A[i]);
    scanf("%d",&M);
    for(int i=1;i<=M;i++) scanf("%d%d",&L[i],&R[i]),id[i]=i;
    sort(id+1,id+M+1,cmp);

    int j=1;
    for(int i=1;i<=N;i++){
        Update(1,1,N,pre[A[i]+100000]+1,i,A[i]);
        pre[A[i]+100000]=i;
        while(R[id[j]]==i&&j<=M) Ans[id[j]]=Query(1,1,N,L[id[j]],R[id[j]]),j++;
    }
    for(int i=1;i<=M;i++) printf("%lld\n",Ans[i].HisMax);

    return 0;
}