CF997E Good Subsegments 题解

· · 题解

本文节选自笔者的另一篇文章：关于一类子区间计和问题

这个做法不需要历史和。

先以子区间最大子段和之和为例讲解具体算法流程。内容有关联，请务必阅读完例题再继续。

单组询问

![](https://cdn.luogu.com.cn/upload/image_hosting/jvck0c27.png) 先写出区间最大子段和的式子表达： $$w(L,R)=\max(\max(ans_L,ans_R),maxsuf_L+maxpre_R)$$ 其中 $ans_L$ 表示在 $[L,mid]$ 中的最大子段和，$ans_R$ 类似，$maxsuf_L$ 表示以 $mid$ 为右端点的最大后缀，$maxpre_R$ 类似。 容易发现上述4种变量都有单调性。考虑对 $ans_L$ 和 $ans_R$ 进行归并，假设当前有 $ans_L \le ans_R$，那么我们就计算以 $L$ 为左端点，$[mid+1,R-1]$ 为右端点的所有区间（例如 $[L,mid+1]$，$[L,mid+2]\dots$）的贡献。 由于已经归并，所以可知 $ans_L\ge ans_{R-1}$，那么 $w(L,R')$ 一定不会取 $ans_{R'}$ 那一项（$R'\in [mid+1,R-1]$）。式子化为： $$\max(ans_L,maxsuf_L+maxpre_{R'})$$ 考虑何时右边取答案，有： $$ans_L\le maxsuf_L+maxpre_{R'}$$ $$ans_L-maxsuf_L\le maxpre_{R'}$$ 于是设第一个满足条件的位置为 $p$，右端点在 $[mid+1,p-1]$ 的答案全是 $ans_L$，在 $[p,R-1]$ 的答案全是 $maxsuf_L+maxpre_{R'}$。求和简易。 事实上，$p$ 随着 $L$ 的移动亦有单调性。此处略证。（由这个性质可以得到 $O(n\log n)$ 的解法） 归并在右边可以对称地写出式子维护，不再赘述。 如果 $p$ 的求取使用 lower_bound 进行，时间复杂度是 $O(n\log^2 n)$ 的。 区间贡献不会算重的简证：一个区间 $[L,R]$ 只会被更晚归并弹出的那个端点计算一次。 ### 多组询问 我们依旧进行归并，但实时地使用线段树（普通的，不需要历史和）维护——截止到目前归并的这个左端点，以某个右端点为下标的贡献总和。 也即给线段树的 $[mid+1,p-1]$ 区间加 $ans_L$，给 $[p,R-1]$ 加上 $maxsuf_L+maxpre_{R'}$。右侧对左侧贡献同理。所以要维护两棵这样的线段树，左右各一棵。 所以线段树要支持区间 $a_i$ 加 $v$，区间 $a_i$ 加上 $b_i$（$maxpre_{R'}$），以及区间求 $a_i$ 的和。 如何回答询问？我们将询问也分治，如果询问在一边直接递归不计算；如果包含了整个区间就不递归等底下分治回来了再回答。 跨过了中点且不包含整个区间的将贡献分四部分：左递归，右递归，左归并，右归并。其中左右递归直接扔下去就可以，左归并指的是当 $L$ 归并到 $query_l$ 后，去线段树上查询 $[mid+1,query_r]$ 的区间和。$query_l$ 指的就是询问的左端点。右同理。（此处是 $L$ 与 $query_l$ 的双指针） 正确性简证：假设一个区间 $[L,R]$ 是由 $L$ 晚归并，那么它的贡献就会算进左归并线段树的下标 $R$ 处。这本质上确实是满足了子区间二维偏序。 询问带来的复杂度可以用类似线段树的复杂度分析得到。总共是 $O((n+q)\log^2 n)

连续子区间计数 （Good Subsegments）

也就是本题。

这题单组询问有一种较为奇妙的转化：考虑将 (i,i+1) 这个数对选不选抽象成一个点。如果原序列上的 i 和 i+1 之间的最值为 mx 和 mn，那么你选了 (i,i+1) 就要选 (mn,mn+1)\dots(mx-1,mx)。于是转化后问题为：每个点对应一条线段，你要计数有多少区间 [L,R] 满足封闭，也即在该区间里的点所对应的所有线段都被这个区间包含。最后还要给答案加 n，因为 i 本身也合法。读者有兴趣可以尝试这个推一推这个做法，但很可惜它难以支持多组询问。

这题套路的做法也要用到结论：区间合法当且仅当 max-min=r-l。我们考虑对前缀最大值归并，然后再 lower_bound 前缀最小值。

设当前归并到 [L,R]，sufmax_L\le premax_R，第一个满足 sufmin_L\ge premin_p 的位置是 p。

对于右端点在 [mid+1,p-1] 的区间，max，min，l 都已知，可以推算出 r 进行单点加。

对于右端点在 [p,R-1] 的区间，max，l 已知，我们要给那些在 [p,R-1] 且 max+l=min+r 的位置进行加一。再次利用结论，我们可以知道这样的位置只可能是 min+r 的最大值所在位（不取等也只能取大于）。所以需要线段树维护 a_i 最大值，a_i 最大值个数，区间 a_i 最大值位置的 b_i 加一（如果为给定的 max+l），区间求 b_i 的和。

反向同理。

提交记录：https://mirror.codeforces.com/problemset/submission/997/301081018

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int INF=1e9+10;

int prec[2][maxn],sufc[2][maxn];
struct SGT{
    int op;
    struct node{
        int l,r;
        long long addv,addw;
        long long sumv;
        int maxv,maxcnt;
    }tr[maxn<<2];
    void pushup(int p){
        tr[p].sumv=tr[p<<1].sumv+tr[p<<1|1].sumv;
        tr[p].maxv=max(tr[p<<1].maxv,tr[p<<1|1].maxv);
        tr[p].maxcnt=0;
        if(tr[p<<1].maxv==tr[p].maxv) tr[p].maxcnt+=tr[p<<1].maxcnt;
        if(tr[p<<1|1].maxv==tr[p].maxv) tr[p].maxcnt+=tr[p<<1|1].maxcnt;
    }
    void addf(int p,long long v,long long w){
        if(tr[p].maxv!=v) return ;
        tr[p].addv=v;tr[p].addw+=w;
        tr[p].sumv+=w*tr[p].maxcnt;
    }
    void pushdown(int p){
        if(tr[p].addw){
            addf(p<<1,tr[p].addv,tr[p].addw);
            addf(p<<1|1,tr[p].addv,tr[p].addw);
            tr[p].addw=0;
        }
    }
    void build(int p,int l,int r){
        tr[p].l=l,tr[p].r=r;tr[p].addw=0;
        if(l==r){
            tr[p].sumv=0;tr[p].maxcnt=1;
            if(op==0) tr[p].maxv=prec[0][tr[p].l];
            else tr[p].maxv=sufc[1][tr[p].l];
            return ;
        }int mid=(tr[p].l+tr[p].r)>>1;
        build(p<<1,l,mid);build(p<<1|1,mid+1,r);pushup(p);
    }
    void add(int p,int l,int r,long long v,long long w){
        if(r<l) return ;
        if(l<=tr[p].l&&tr[p].r<=r) return addf(p,v,w);
        int mid=(tr[p].l+tr[p].r)>>1;pushdown(p);
        if(l<=mid) add(p<<1,l,r,v,w);
        if(mid<r) add(p<<1|1,l,r,v,w);pushup(p);
    }
    void add(int p,int pos,long long v){
        if(tr[p].l==tr[p].r) return void(tr[p].sumv+=v);
        int mid=(tr[p].l+tr[p].r)>>1;pushdown(p);
        if(pos<=mid) add(p<<1,pos,v);
        else add(p<<1|1,pos,v);pushup(p);
    }
    long long query(int p,int l,int r){
        if(r<l) return 0ll;
        if(l<=tr[p].l&&tr[p].r<=r) return tr[p].sumv;
        int mid=(tr[p].l+tr[p].r)>>1;pushdown(p);
        if(r<=mid) return query(p<<1,l,r);
        if(mid<l) return query(p<<1|1,l,r);
        return query(p<<1,l,r)+query(p<<1|1,l,r);
    }
}tr[2];

struct qry{
    int l,r,id;
};long long ans[maxn];
int n,m;
int a[maxn];
int premax[maxn],sufmax[maxn];
int premin[maxn],sufmin[maxn];
long long cdq(int l,int r,vector<qry> q){
    if(l==r){
        for(qry p:q) ans[p.id]++;
        return 1;
    }int mid=(l+r)>>1;
    for(qry &p:q) p.l=max(p.l,l),p.r=min(p.r,r);//!!!

//  printf("cdq in:%d %d\n",l,r);
//  for(qry p:q) printf("q:%d %d %d\n",p.l,p.r,p.id);

    premax[mid]=0;premin[mid]=INF;
    for(int i=mid+1;i<=r;i++){
        premax[i]=max(premax[i-1],a[i]);
        premin[i]=min(premin[i-1],a[i]);
        prec[0][i]=premin[i]+i;
        prec[1][i]=premax[i]-i;
    }
    sufmax[mid+1]=0;sufmin[mid+1]=INF;
    for(int i=mid;i>=l;i--){
        sufmax[i]=max(sufmax[i+1],a[i]);
        sufmin[i]=min(sufmin[i+1],a[i]);
        sufc[0][i]=sufmax[i]+i;
        sufc[1][i]=sufmin[i]-i;
    }

    tr[0].build(1,mid+1,r);
    tr[1].build(1,l,mid);
    vector<qry> lq,rq;
    for(qry p:q){
        if(p.l<=l&&r<=p.r) continue;
        if(p.l<=mid&&mid<p.r) lq.push_back(p),rq.push_back(p);
    }
    sort(lq.begin(),lq.end(),[](qry x,qry y){return x.l>y.l;});
    sort(rq.begin(),rq.end(),[](qry x,qry y){return x.r<y.r;});

    int p1=mid,p2=mid+1;
    int lp=0,rp=0;
    while(p1>=l&&p2<=r){
        if(sufmax[p1]<=premax[p2]){
            int p=lower_bound(premin+mid+1,premin+(p2-1)+1,sufmin[p1],greater<int>())-premin;
            int np=sufc[0][p1]-sufmin[p1];
            if(mid+1<=np&&np<p) tr[0].add(1,np,1);
            tr[0].add(1,p,p2-1,sufc[0][p1],1);
            while(lp<(int)lq.size()&&lq[lp].l>=p1){
                ans[lq[lp].id]+=tr[0].query(1,mid+1,lq[lp].r);
                lp++;
            }p1--;
        }else{
            int p=upper_bound(sufmin+(p1+1),sufmin+mid+1,premin[p2])-sufmin-1;
            int np=premin[p2]-prec[1][p2];
            if(p<np&&np<=mid) tr[1].add(1,np,1);
            tr[1].add(1,p1+1,p,prec[1][p2],1);
            while(rp<(int)rq.size()&&rq[rp].r<=p2){
                ans[rq[rp].id]+=tr[1].query(1,rq[rp].l,mid);
                rp++;
            }p2++;
        }
    }
    while(p1>=l){
        int p=lower_bound(premin+mid+1,premin+p2,sufmin[p1],greater<int>())-premin;
        int np=sufc[0][p1]-sufmin[p1];
        if(mid+1<=np&&np<p) tr[0].add(1,np,1);
        tr[0].add(1,p,p2-1,sufc[0][p1],1);
        while(lp<(int)lq.size()&&lq[lp].l>=p1){
            ans[lq[lp].id]+=tr[0].query(1,mid+1,lq[lp].r);
            lp++;
        }p1--;
    }
    while(p2<=r){
        int p=upper_bound(sufmin+(p1+1),sufmin+mid+1,premin[p2])-sufmin-1;
        int np=premin[p2]-prec[1][p2];
        if(p<np&&np<=mid) tr[1].add(1,np,1);
        tr[1].add(1,p1+1,p,prec[1][p2],1);
        while(rp<(int)rq.size()&&rq[rp].r<=p2){
            ans[rq[rp].id]+=tr[1].query(1,rq[rp].l,mid);
            rp++;
        }p2++;
    }
    long long nowv=tr[0].query(1,mid+1,r)+tr[1].query(1,l,mid);

    lq.clear(),rq.clear();
    for(qry p:q){
        int L=p.l,R=p.r;
        if(L<=l&&r<=R) continue;
        if(L<=mid) lq.push_back(p);
        if(mid<R) rq.push_back(p);
    }long long res=cdq(l,mid,lq)+cdq(mid+1,r,rq)+nowv;
    for(qry p:q) if(p.l<=l&&r<=p.r) ans[p.id]+=res;
//  printf("cdq out:%d %d\n",l,r);
//  printf("res:%lld\n",res);
    return res;
}
vector<qry> qr;
int main(){
    scanf("%d",&n);tr[0].op=0;tr[1].op=1;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i=1,l,r;i<=m;i++) scanf("%d%d",&l,&r),qr.push_back({l,r,i});
    cdq(1,n,qr);
    for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
    return 0;
}