题解：AT_abc324_g [ABC324G] Generate Arrays

INF_SZG · 2026-10-20 09:51:55 · 题解

可以使用小波树。

原排列 A 是 1 \sim N 的排列，所以我们反过来记：

其中 val 表示数值，pos 表示位置。也就是 p[a[i]] = i。这样“值在某个区间、位置在某个区间里有多少个数”就变成一个二维数点问题。用小波树可以很快查。

小波树

小波树可以理解成：把数组按每个数的二进制位从高到低做稳定划分，每一层记录前缀 0 的个数。稳定划分就是：这一位（从高往低的二进制位）是 0 的放前面，这一位是 1 的放后面，而且原来的相对顺序不变。

这题我们把“值”当下标，把“位置”当数组里的值，然后在 p[1 \sim N] 上建树，按位置的二进制位划分即可。

复杂度大概是

空间是

划分：

拿一个小例子，设：

值下标:   1   2   3   4   5   6   7
p[值]:    3   1   4   2   7   5   6
二进制:  011 001 100 010 111 101 110

最高位就是二进制里的 bit2，也就是 4 这一位。

值下标:   1   2   3   4   5   6   7
p值:    3   1   4   2   7   5   6
二进制:  011 001 100 010 111 101 110
最高位:   0   0   1   0   1   1   1

稳定划分后：
0 :  3  1  2      （对应值下标 1,2,4）
1 :  4  7  5  6   （对应值下标 3,5,6,7）

这一层的 pv[0] 记录前缀 0 的个数：

然后按照次高位一直划分……

画成树大概这样：

操作：

具体地

• 新数列值区间是 $[\max(V, x+1), W]$，原数列值区间变成 $[V, \min(W, x)]$。
• --- 核心就是把数列抽象成矩形，然后用小波树在矩形里数点和找第 $k$ 个位置。写的时候注意 $t=1$ 的边界：$x \le 0$ 是全部拿走，$x \ge C$ 是新数列空，不然就找切点。$t=2$ 就简单一点，直接改值区间的上下界。

详见代码

:::info[Code]{open}

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,q,K;
int a[N],p[N];
int pv[18][N];//小波树每层前缀 0 的个数
int lv[2][N];//滚动数组，存每层稳定划分后的位置序列
int bl[N],br[N],cl[N],cr[N];//第 i 个数列的位置区间和值区间
int clt(int l,int r,int t){//值区间[l,r]里，位置 <= t 的个数
    if(l>r)return 0; // 空区间!!!!
    int rs=0;
    for(int d=0;d<K;++d){//从高位到低位走小波树
        int md=K-1-d;
        if((t>>md)&1){
            rs+=pv[d][r]-pv[d][l-1];
            int nl=pv[d][n]+(l-1)-pv[d][l-1]+1;
            r=pv[d][n]+r-pv[d][r];
            l=nl;
        }else{//t这一位是0只能去左
            int nl=pv[d][l-1]+1;
            r=pv[d][r];
            l=nl;//更新左端点
        }
        if(l>r)break;
    }
    if(l<=r)rs+=r-l+1;//最后剩下的都满足
    return rs;
}
int kth(int l,int r,int k){//值区间 [l,r] 里第 k 个位置
    int rs=0;
    for(int d=0;d<K;++d){
    //    int md=K-1-d;
        int z=pv[d][r]-pv[d][l-1];
        if(k<=z){
            r=pv[d][r];
            l=pv[d][l-1]+1;
            rs<<=1;// 当前位填0
        }else{
            k-=z;
            l=pv[d][n]+(l-1)-pv[d][l-1]+1;
            r=pv[d][n]+r-pv[d][r];
            rs=(rs<<1)|1;//当前位填 1
        }
    }
    return rs;
}
int cnt(int l,int r,int x,int y){//值区间 [l,r] 中位置在 [x,y] 的个数
    if(l>r||x>y)return 0;
    return clt(l,r,y)-clt(l,r,x-1);//前缀香煎
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        p[a[i]]=i;
    }
    while((1<<K)<=n)K++;//算二进制位数
    for(int i=1;i<=n;++i)lv[0][i]=p[i];
    for(int d=0;d<K;++d){
        int md=K-1-d;
        int*ca=lv[d&1],*cb=lv[(d+1)&1];// 当前层数组和下一层(滚动)
        pv[d][0]=0;
        for(int j=1;j<=n;++j)pv[d][j]=pv[d][j-1]+1-((ca[j]>>md)&1);
        int p0=1,p1=pv[d][n]+1;//前缀0，1的指针
        for(int j=1;j<=n;++j){
            if((ca[j]>>md)&1)cb[p1++]=ca[j];
            else cb[p0++]=ca[j];
        }
    }
    cin>>q;
    bl[0]=1;br[0]=n;cl[0]=1;cr[0]=n;
    for(int i=1;i<=q;++i){
        int t,s,x;
        cin>>t>>s>>x;
        int L=bl[s],R=br[s],V=cl[s],W=cr[s];//分别表示位置的左右端点和值的左右端点
        int an=0;
        if(t==2){
            int nl=V;
            if(x+1>nl)nl=x+1;
            an=cnt(nl,W,L,R);
            bl[i]=L;br[i]=R;cl[i]=nl;cr[i]=W;
            if(x<W)cr[s]=x;
        }else{
            if(x<=0){
                an=cnt(V,W,L,R);
                bl[i]=L;br[i]=R;cl[i]=V;cr[i]=W;
                bl[s]=1;br[s]=0;
            }else{
                int C=cnt(V,W,L,R);
                if(x>=C){
                    bl[i]=1;br[i]=0;cl[i]=1;cr[i]=0;
                }else{
                    int c1=clt(V,W,L-1);
                    int c=kth(V,W,c1+x);
                    an=C-x;
                    bl[i]=c+1;br[i]=R;cl[i]=V;cr[i]=W;
                    br[s]=c;
                }
            }
        }
        cout<<an<<"\n";
    }
    return 0;
}

:::