luogu P2617 Dynamic Rankings 主席树套树状数组模板

题目链接

树套树模板

#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int,int>
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 1e5 + 3;
const LL mod = 1e9 + 7;
int n,m,a[N],b[N<<1],cnT,tot,now,T[N<<1],Q[N*170],cnt;
struct uzi{int sta;char x;int l,r,k;}p[N];
int newnode(){int p=tot?Q[tot--]:++cnT;return p;}
struct faker{int sum,l,r;}t[N*170];
void up(int &x,int y,int l,int r,int pos,int val){
    if(!x){x=newnode();t[x].sum=t[x].l=t[x].r=0;}
    t[x]=t[y];t[x].sum+=val;
    if(l==r)return ;int mid=l+r>>1;
    if(pos<=mid)up(t[x].l,t[y].l,l,mid,pos,val);
    else up(t[x].r,t[y].r,mid+1,r,pos,val);
    if(!t[x].sum)Q[++tot]=x,x=0;
}
int totx,toty;
int L[100],R[100];
int get(int l,int r,int x){
    if(l==r)return l;
    int Y=0;
    int mid=l+r>>1;
    for(int i=1;i<=toty;i++)Y+=t[t[R[i]].l].sum;
    for(int i=1;i<=totx;i++)Y-=t[t[L[i]].l].sum;
    if(Y>=x){
        for(int i=1;i<=toty;i++)R[i]=t[R[i]].l;
        for(int i=1;i<=totx;i++)L[i]=t[L[i]].l;
        return get(l,mid,x);
    }
    else{
        for(int i=1;i<=toty;i++)R[i]=t[R[i]].r;
        for(int i=1;i<=totx;i++)L[i]=t[L[i]].r;
        return get(mid+1,r,x-Y);
    }
}
int main() {
	ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i],b[++cnt]=a[i];
    for(int i=1;i<=m;i++){
        int l,r,k;
        char x;
        cin>>x;
        if(x=='Q'){
            cin>>l>>r>>k;
            p[i]={0,x,l,r,k};
        }else {
            cin>>l>>r;
            p[i]={1,x,l,r,0};
            b[++cnt]=r;
        }
    }
    sort(b+1,b+1+cnt);
    cnt=unique(b+1,b+1+cnt)-b-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;
    for(int i=1;i<=m;i++)if(p[i].sta)p[i].r=lower_bound(b+1,b+1+cnt,p[i].r)-b;
    for(int i=1;i<=n;i++)for(int j=i;j<=n;j+=j&-j)up(T[j],T[j],1,cnt,a[i],1);
    for(int i=1;i<=m;i++){
        if(!p[i].sta){
            totx=toty=0;
            for(int j=p[i].l-1;j;j-=j&-j)L[++totx]=T[j];
            for(int j=p[i].r;  j;j-=j&-j)R[++toty]=T[j];
            //cout<<get(1,cnt,p[i].k)<<' ';
            cout<<b[get(1,cnt,p[i].k)]<<endl;
        }else{
            for(int j=p[i].l;j<=n;j+=j&-j)up(T[j],T[j],1,cnt,a[p[i].l],-1);
            a[p[i].l]=p[i].r;
            for(int j=p[i].l;j<=n;j+=j&-j)up(T[j],T[j],1,cnt,p[i].r,1);
        }
    }
	return 0;
}