题解：CF1967F Next and Prev

luckydrawbox · 2024-11-04 20:43:52 · 题解

\text{Link}

题意

设 p 是一个排列，对于 q=1,2,\cdots,n，记 p' 是 p 只保留小于等于 q 的值构成的子序列，pre_i 是 p' 中上一个比 {p'}_i 大的值的位置，nxt_i 是 p' 中下一个比 {p'}_i 大的值的位置，不存在分别是 -\infin,\infin。对每个 q 给出一些 x，求 \sum_{i=1}^q\min(nxt_i-pre_i,x)。

分析

这里提供一个不用推式子的严格最劣解。

考虑暴力怎么做，我们每次插入一个新的值，看他会对其他位置的 pre、nxt 产生什么影响。显然，左边受他影响的点形成了一个递减的单调栈，右边受他影响的点形成了一个递增的单调栈，于是，我们暴力更新这些 pre、nxt，用数据结构维护答案即可,复杂度 O(n^2\log n)。

要优化这个过程，我们可以分块处理每个块中的单调栈，对于块外的修改，我们更新块内单调栈的信息；对于块内的修改，我们暴力重构块。注意到每次 q 增加都要插入一个点，所以这里使用块状链表。

块内信息

限定块长不超过 B，实际块长为 len，块内的点按原数组中的顺序编号为 1\sim len，bl,br 表示块内最左、最右点。

我们依据块内点的相对大小关系，将他们分为四类（图比较丑，大家意会一下就行）：

1. 红点：块内的极大值点，在块内其左右两边都没有比他大的值。
2. 绿点：满足左侧没有比其大的值，右侧有比其大的值的点。特别的，不包括红点。显然绿点的值从左至右单调递增。
3. 蓝点：满足左侧有比其大的值的点，右侧没有比其大的值。特别的，不包括红点。显然蓝点的值从左至右单调递减。
4. 紫点：不属于上面三类点的点，左右两侧均有比其大的点。

这几类点都可以预处理得到。

先考虑块外的修改对块内的影响，现在另外某个块内新加入了一个极大值 u_1，由于当前块与极大值位置之间已经形成了单调栈，栈中极大值为 u_2，所以本块内只有值在 (u_2,u_1) 之间的点的 pre/nxt 会被修改。然后是分类讨论：

1. 对红点：一个块只有一个红点，所以暴力更新它即可。
2. 对绿点：若极大值位置在块左侧，更新的 pre 在绿点中是一段后缀，可以用线段树维护。nxt 固定不变。
3. 对蓝点：若极大值位置在块右侧，更新的 nxt 在蓝点中是一段前缀，可以用线段树维护；pre 固定不变。
4. 对紫点：其 pre,nxt 均不变。

询问等价于我们要求出 nxt_i-pre_i\le x 的 nxt_i-pre_i 的和，以及 nxt_i-pre_i> x 的 i 的个数。

下面是一些细节：

紫点是好处理的，我们可以在重构时求出它在块内的 pre,nxt，再将 nxt-pre 排个序，查询时对每个块分别查询，单次复杂度 O((B+\frac nB)\log B)，注意到值不超过 B，所以可以桶排序做到修改 O(B)，查询 O(\frac nB)。

对于绿点，我们预处理出其 nxt'_i，为其 nxt_i 在块内的编号，同时维护其 pre'_i，表示 pre_i 到 bl 的距离 -1，显然 nxt_i-pre_i=nxt'_i+pre'_i。这样的好处是，块外点对绿点的影响就变成了对 pre'_i 的区间覆盖。然后考虑查询，注意到随着 i 的增大，绿点 i 的值 p'_i 也增大，因此 pre'_i，又由于 nxt'_i 显然增大，所以 pre'_i+nxt'_i 是单调递增的，于是我们可以在线段树上二分出 x 对应的位置，再统计和即可。单次修改/查询时间复杂度 O(\frac nB\log B)。对于蓝点也同理，只是 pre'_i,nxt'_i 的定义略有不同。

块重构与分裂

重构是容易的，就是预处理上述信息，线段树也可以线性建树。时间复杂度 O(B)。

当块长超过限定长度时，需要分裂块，这实际上并不容易，pre、nxt 的信息部分可以保留，部分要加上一些长度值，这里就不赘述了。时间复杂度 O(B)。

最终时间复杂度 O((n+k)(B+\frac nB\log B))，理论最优为 O((n+k)\sqrt {n\log n})，但显然常数巨大，排到了最劣解，要极限卡常才能过，瓶颈在于线段树和在绿、蓝点集合中查询后继。

代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define ll long long
using namespace std;
long long read(){
    long long x=0,f=1;char ch=getchar();
    while(!isdigit(ch))
    {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
void write(long long x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int N=3e5+10,M=1010,U=800+10,inf=1e7;
int T,n,pi[N],rp[N];
int tiao=0;
#define pl p<<1
#define pr p<<1|1
struct Block_list{
    int B=900;
    int tot=1;
    struct Block{
        //upd outside
        int len,head,tail;
        int pre[M],nxt[M],b[M];
        //upd inside
        int zl[M],zr[M],tpl,tpr,bl,br;
        int z[M],tp,mxid,tv;
        ll val[M],cal[M];
        bool out[M];
        struct Segment{
            int tag[M<<2],mx[M<<2],mx1[M<<2];
            ll sum[M<<2],sum1[M<<2];
            int *f,*g,*a;
            void pushup(int p){
                mx[p]=max(mx[pl],mx[pr]);
                sum[p]=sum[pl]+sum[pr];
            }
            void pushdown(int p,int l,int mid,int r){
                if(tag[p]!=-1){
                    mx[pl]=mx1[pl]+tag[p];
                    mx[pr]=mx1[pr]+tag[p];
                    sum[pl]=sum1[pl]+(mid-l+1ll)*tag[p];
                    sum[pr]=sum1[pr]+(r-(mid+1)+1ll)*tag[p];
                    tag[pl]=tag[pr]=tag[p];
                    tag[p]=-1;
                }
            }
            void build(int p,int L,int R){
                if(L>R)return;
                tag[p]=-1;
                if(L==R){
                    tag[p]=g[a[L]];
                    sum1[p]=mx1[p]=f[a[L]];
                    sum[p]=mx[p]=f[a[L]]+g[a[L]];
                    return;
                }
                int mid=(L+R)>>1;
                build(pl,L,mid);build(pr,mid+1,R);
                mx1[p]=max(mx1[pl],mx1[pr]);
                sum1[p]=sum1[pl]+sum1[pr];
                pushup(p);
            }
            void change(int p,int l,int r,int v,int L,int R){
                if(l>r||L>R)return;
                if(l<=L&&R<=r){
                    tag[p]=v;mx[p]=mx1[p]+v;
                    sum[p]=sum1[p]+(R-L+1ll)*v;
                    return;
                }
                int mid=(L+R)>>1;
                pushdown(p,L,mid,R);
                if(l<=mid)change(pl,l,r,v,L,mid);
                if(r>mid)change(pr,l,r,v,mid+1,R);
                pushup(p);
            }
            ll ask(int p,int x,int L,int R){
                if(L>R)return 0;
                if(L==R)return min(mx[p],x);
                int mid=(L+R)>>1;
                pushdown(p,L,mid,R);
                if(mx[pl]<=x)return sum[pl]+ask(pr,x,mid+1,R);
                return 1ll*(R-mid)*x+ask(pl,x,L,mid);
            }
            void update(int p,int L,int R){
                if(L>R)return;
                if(L==R){
                    g[a[L]]=tag[p];
                    return;
                }
                int mid=(L+R)>>1;
                pushdown(p,L,mid,R);
                update(pl,L,mid);update(pr,mid+1,R);
            }
        }tl,tr;
        void init(){
            bl=b[1];br=b[len];
            for(int i=1;i<=len;i++)out[i]=0;
            tpl=tpr=tp=0;
            zl[tpl=1]=1;out[1]=1;
            z[tp=1]=1;
            for(int i=2;i<=len;i++){
                if(pi[b[zl[tpl]]]<pi[b[i]])out[zl[++tpl]=i]=1;
                while(tp&&pi[b[z[tp]]]<pi[b[i]])tp--;
                if(tp)pre[i]=z[tp];
                z[++tp]=i;
            }
            mxid=zl[tpl];
            zr[tpr=1]=len;out[len]=1;
            z[tp=1]=len;
            for(int i=len-1;i>=1;i--){
                if(pi[b[zr[tpr]]]<pi[b[i]])out[zr[++tpr]=i]=1;
                while(tp&&pi[b[z[tp]]]<pi[b[i]])tp--;
                if(tp)nxt[i]=z[tp];
                z[++tp]=i;
            }
            for(int i=1;i<tpr;i++)pre[zr[i]]=len-pre[zr[i]];
        }
        void build(){
            init();
            tv=0;
            for(int i=1;i<=len;i++)val[i]=cal[i]=0;
            for(int i=2;i<len;i++)
                if(!out[i]){
                    val[nxt[i]-pre[i]]+=nxt[i]-pre[i];
                    cal[nxt[i]-pre[i]]++;
                }
            for(int i=1;i<=len;i++)
                val[i]=val[i-1]+val[i],cal[i]=cal[i-1]+cal[i];
            tl.a=zl;tl.f=nxt;tl.g=pre;
            tr.a=zr;tr.f=pre;tr.g=nxt;
            tl.build(1,1,tpl-1);tr.build(1,1,tpr-1);
        }
        void destruct(){
            tl.update(1,1,tpl-1);tr.update(1,1,tpr-1);
        }
        void cut(int lim){
            for(int i=1;i<=lim;i++){
                if(!out[i]||i<mxid){
                    if(nxt[i]>lim&&nxt[i]<=len){
                        nxt[i]=nxt[i]-lim;
                    }
                }
                else if(i>mxid){
                    nxt[i]+=len-lim;
                }
            }
            for(int i=lim+1;i<=len;i++){
                if(!out[i]){
                    if(pre[i]<=lim)pre[i]=lim-pre[i];
                }
                else if(i>mxid){
                    if(len-pre[i]<=lim){
                        pre[i]=lim-(len-pre[i]);
                    }
                }
                else if(i<mxid){
                    pre[i]+=lim;
                }
            }
            if(mxid<=lim)nxt[mxid]+=len-lim;
            else pre[mxid]+=lim;
        }
        int find(int *a,int l,int r,int x){
            while(l<r){
                int mid=(l+r)>>1;
                if(pi[b[a[mid]]]>=x)r=mid;
                else l=mid+1;
            }
            return l;
        }
        void modify(int ty,int x,int d){
            if(x>pi[b[mxid]])return;
            if(!ty){
                pre[mxid]=d;
                tl.change(1,find(zl,1,tpl,x),tpl-1,d,1,tpl-1);
            }
            else{
                nxt[mxid]=d;
                tr.change(1,find(zr,1,tpr,x),tpr-1,d,1,tpr-1);
            }
        }
        ll query(int x){
            //printf("query:");
            return min(nxt[mxid]+pre[mxid]+len,x)+tl.ask(1,x,1,tpl-1)+tr.ask(1,x,1,tpr-1)
            +val[min(x,len)]+(cal[len]-cal[min(x,len)])*x;
        }
    }a[U];
    void split(int p,int pos){
        int q=++tot,lim=a[p].len/2;
        a[p].cut(lim);
        a[q].len=a[p].len-lim;
        a[p].len=lim;
        for(int i=1;i<=a[q].len;i++){
            a[q].b[i]=a[p].b[a[p].len+i];
            a[q].pre[i]=a[p].pre[a[p].len+i];
            a[q].nxt[i]=a[p].nxt[a[p].len+i];
        }
        a[a[p].tail].head=q;
        a[q].tail=a[p].tail;
        a[q].head=p;a[p].tail=q;
        a[p].build();a[q].build();
    }
    int insert(int p,int t){
        a[p].destruct();
        int pos=a[p].len+1;
        for(int i=a[p].len;i>=1;i--){
            if(a[p].b[i]>t){
                a[p].b[i+1]=a[p].b[i];
                a[p].pre[i+1]=a[p].pre[i];
                a[p].nxt[i+1]=a[p].nxt[i];
                pos=i;
            }
            else break;
        }
        a[p].b[pos]=t;a[p].len++;
        a[p].pre[pos]=a[p].nxt[pos]=inf;
        if(a[p].len>B){
            //a[p].build();
            a[p].init();
            split(p,pos);
            return t<=a[p].br?p:a[p].tail;
        }
        else {
            a[p].build();
            return p;
        }
    }
    void update(int t){
        int p;
        for(int i=1;i;i=a[i].tail){
            if(!a[i].tail||a[a[i].tail].bl>t){
                p=i;break;
            }
        }
        p=insert(p,t);
        int pos=0;
        for(int i=1;i<=a[p].len;i++){
            if(a[p].b[i]==t){
                pos=i;break;
            }
        }
        int d=a[p].len-pos,mx=0;
        if(a[p].tpr>1)mx=pi[a[p].b[a[p].zr[a[p].tpr-1]]];
        for(int i=a[p].tail;i;i=a[i].tail){
            a[i].modify(0,mx,d);
            d+=a[i].len;mx=max(mx,pi[a[i].b[a[i].mxid]]);
        }
        d=pos;mx=0;
        if(a[p].tpl>1)mx=pi[a[p].b[a[p].zl[a[p].tpl-1]]];
        for(int i=a[p].head;i;i=a[i].head){
            a[i].modify(1,mx,d);
            d+=a[i].len;mx=max(mx,pi[a[i].b[a[i].mxid]]);
        }
    }
    ll ask(int x){
        ll ans=0;
        for(int i=1;i;i=a[i].tail)ans+=a[i].query(x);
        return ans;
    }
}K;
ll pans[N];
int vx[N];
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int cnt=0;
    T=read();
    while(T--){
        n=read();
        for(int i=1;i<=n;i++){
            pi[i]=read();
            rp[pi[i]]=i;
        }
        K.tot=1;K.B=900;
        K.a[1].head=K.a[1].tail=K.a[1].len=0;
        for(int i=1;i<=n;i++){
            K.update(rp[i]);
            int k=read();cnt+=k;
            K.B=min(1000,max((int)sqrt(i)*2,800));
            for(int j=1;j<=k;j++){
                int x=read();
                vx[j]=x;
                if(pans[x]){
                    write(pans[x]);putchar('\n');
                    continue;
                }
                write(pans[x]=K.ask(x));putchar('\n');
            }
            for(int j=1;j<=k;j++)pans[vx[j]]=0;
        }
    }
    return 0;
}