洛谷 2617 带修主席树

带修改主席树的模板题

主席树和树状数组都是维护前缀和，树状数组的每一个结点表示一颗权值线段树，当然要动态开点
每次修改 $p o s$ ，则将 $p o s, p o s + l o w b i t (p o s) . . .$ 一并修改
询问时，用到 $p o s, p o s - l o w b i t (p o s) . . .$ 存起来，整体在线段树中向左右儿子移动

代码

#include<bits/stdc++.h>
#define N 200010
#define INF 0x3f3f3f3f
#define eps 1e-7
#define pi 3.141592653589793
#define mod 998244353
// #define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x,y) memset(x,0,sizeof(int)*(y+3))
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// uniform_real_distribution<double> dis(-1.0,1.0);

int a[N],f[N];
char op[3];
int q[N],ql[N],qr[N],qk[N];
int rt[N],tot,n,m,cnt;
struct PST{
    int ls[N*200],rs[N*200],sum[N*200],tp[2][20],p[2],cnt;
    void init(int Max){cnt=0;tot=Max;}
    void ins(int &i,int x,int val,int l=1,int r=tot){
        if (!i) i=++cnt; sum[i]+=val;
        if (l==r) return; int mid=l+r>>1;
        if (x<=mid) ins(ls[i],x,val,l,mid);
        else ins(rs[i],x,val,mid+1,r);
    }
    inline void Modify(int pos,int val){
        int x=lb(f+1,f+tot+1,a[pos])-f;
        for(int i=pos;i<=n;i+=i&-i) ins(rt[i],x,val);
    }
    int ask(int k,int l=1,int r=tot){
        if (l==r) return l; int mid=l+r>>1,s=0;
        for(int i=1;i<=p[1];i++) s+=sum[ls[tp[1][i]]];
        for(int i=1;i<=p[0];i++) s-=sum[ls[tp[0][i]]];
        if (k<=s){
            for(int j=0;j<2;j++) for(int i=1;i<=p[j];i++) tp[j][i]=ls[tp[j][i]];
            return ask(k,l,mid);
        }else{
            for(int j=0;j<2;j++) for(int i=1;i<=p[j];i++) tp[j][i]=rs[tp[j][i]];
            return ask(k-s,mid+1,r);
        }
    }
    inline int query(int l,int r,int k){
        p[0]=p[1]=0; 
        for(int i=r;i;i-=i&-i) tp[1][++p[1]]=rt[i];
        for(int i=l-1;i;i-=i&-i) tp[0][++p[0]]=rt[i];
        return ask(k);
    }
}PST;

int main()
{
    scc(n,m); 
    for(int i=1;i<=n;i++) sc(a[i]),f[++cnt]=a[i];
    for(int i=1;i<=m;i++){
        scanf("%s",op); q[i]=(op[0]=='Q');
        if(q[i]) sccc(ql[i],qr[i],qk[i]);
        else scc(ql[i],qr[i]),f[++cnt]=qr[i];
    }
    sort(f+1,f+cnt+1);
    cnt=unique(f+1,f+cnt+1)-f-1;
    PST.init(cnt);
    for(int i=1;i<=n;i++) PST.Modify(i,1);
    for(int i=1;i<=m;i++){
        if (q[i]) printf("%d\n",f[PST.query(ql[i],qr[i],qk[i])]);
        else{
            PST.Modify(ql[i],-1);
            a[ql[i]]=qr[i];
            PST.Modify(ql[i],1);
        }
    }
    return 0;
}