P3369 【模板】普通平衡树

#include <bits/stdc++.h>
#define int long long
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;

const int N = 1e5+5;
const int MOV = 1e7;

struct node{
    int v,l,r;
} t[N<<4];
int tot,root;

inline void newnode(int &i){
    if(!i) i=(++tot);
}

void update(int p,int v,int &i,int l,int r){
    newnode(i);
    t[i].v+=v;
    if(l==r){
        if(t[i].v<0) t[i].v=0;
        return;
    }
    if(p<=mid) update(p,v,ls,l,mid);
    else update(p,v,rs,mid+1,r);
}

int rnk(int ql,int qr,int &i,int l,int r){
    if(!i) return 0;
    if(ql<=l&&r<=qr) return t[i].v;
    int ans=0;
    if(ql<=mid) ans+=rnk(ql,qr,ls,l,mid);
    if(qr>mid) ans+=rnk(ql,qr,rs,mid+1,r);
    return ans;
}

int kth(int k,int &i,int l,int r){
    if(l==r) return l;
    if(t[ls].v>=k) return kth(k,ls,l,mid);
    else return kth(k-t[ls].v,rs,mid+1,r);
}

int n;

signed main(){
    cin>>n;
    while(n--){
        int op,x;
        cin>>op>>x;
        if(op==1) update(x+MOV,1,root,1,MOV<<1);
        if(op==2) update(x+MOV,-1,root,1,MOV<<1);
        if(op==3) cout<<(rnk(1,x+MOV-1,root,1,MOV<<1)+1)<<'\n';
        if(op==4) cout<<(kth(x,root,1,MOV<<1)-MOV)<<'\n';
        if(op==5) cout<<(kth(rnk(1,x+MOV-1,root,1,MOV<<1),root,1,MOV<<1)-MOV)<<'\n';
        if(op==6) cout<<(kth(rnk(1,x+MOV,root,1,MOV<<1)+1,root,1,MOV<<1)-MOV)<<'\n';
    }
    return 0;
}

P3834 【模板】可持久化线段树 2

#include <bits/stdc++.h>
#define int long long
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;

const int N = 2e5+5;

struct node{
    int v,l,r;
} t[N<<5];
int tot,root[N];

inline void newnode(int &i){
    t[++tot]=t[i];i=tot;
}

void update(int p,int v,int &i,int l,int r){
    newnode(i);
    t[i].v+=v;
    if(l==r) return;
    if(p<=mid) update(p,v,ls,l,mid);
    else update(p,v,rs,mid+1,r);
}

int query(int ql,int qr,int k,int l,int r){
    if(l==r) return l;
    int delta=t[t[qr].l].v-t[t[ql].l].v;
    if(delta>=k) return query(t[ql].l,t[qr].l,k,l,mid);
    else return query(t[ql].r,t[qr].r,k-delta,mid+1,r);
}

int n,m,a[N],b[N];

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) b[i]=a[i];
    sort(b+1,b+n+1);
    int top=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++){
        int p=root[i-1];
        update(lower_bound(b+1,b+top+1,a[i])-b,1,root[i-1],1,top);
        root[i]=root[i-1],root[i-1]=p;
    }
    while(m--){
        int l,r,k;
        cin>>l>>r>>k;
        cout<<b[query(root[l-1],root[r],k,1,top)]<<'\n';
    }
    return 0;
}

P3567 [POI2014]KUR-Couriers

#include <bits/stdc++.h>
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;

const int N = 5e5+5;

struct node{
    int v,l,r;
} t[N<<5];
int tot,root[N];

inline void newnode(int &i){
    t[++tot]=t[i];i=tot;
}

void update(int p,int v,int &i,int l,int r){
    newnode(i);
    t[i].v+=v;
    if(l==r) return;
    if(p<=mid) update(p,v,ls,l,mid);
    else update(p,v,rs,mid+1,r);
}

int query(int ql,int qr,int v,int l,int r){
    if(l==r) return l;
    int lsiz=t[t[qr].l].v-t[t[ql].l].v,rsiz=t[t[qr].r].v-t[t[ql].r].v;
    if((lsiz<<1)>v) return query(t[ql].l,t[qr].l,v,l,mid);
    if((rsiz<<1)>v) return query(t[ql].r,t[qr].r,v,mid+1,r);
    return 0;
}

int n,m,a[N];

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        int p=root[i-1];
        update(a[i],1,root[i-1],1,n);
        root[i]=root[i-1],root[i-1]=p;
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<query(root[l-1],root[r],r-l+1,1,n)<<'\n';
    }
    return 0;
}

P1972 [SDOI2009] HH的项链

#include <bits/stdc++.h>
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;

const int N = 1e6+5;

struct node{
    int v,l,r;
} t[N<<5];
int tot,root[N];

inline void newnode(int &i){
    t[++tot]=t[i];i=tot;
}

int update(int p,int v,int i,int l,int r){
    newnode(i);
    t[i].v+=v;
    if(l==r) return i;
    if(p<=mid) ls=update(p,v,ls,l,mid);
    else rs=update(p,v,rs,mid+1,r);
    return i;
}

int query(int ql,int qr,int vl,int vr,int l,int r){
    if(ql<=l&&r<=qr) return t[vr].v-t[vl].v;
    int res=0;
    if(ql<=mid) res+=query(ql,qr,t[vl].l,t[vr].l,l,mid);
    if(qr>mid) res+=query(ql,qr,t[vl].r,t[vr].r,mid+1,r);
    return res;
}

int n,m,a[N],last[N],top[N];

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        last[i]=top[a[i]];
        top[a[i]]=i;
    }
    for(int i=1;i<=n;i++) root[i]=update(last[i],1,root[i-1],0,n);
    cin>>m;
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<(r-l+1-query(l,r,root[l-1],root[r],0,n))<<'\n';
    }
    return 0;
}

P4587 [FJOI2016]神秘数

#include <bits/stdc++.h>
#define int long long
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;

const int N = 2e5+5;

struct node{
    int v,l,r;
} t[N<<5];
int tot,root[N];

inline void newnode(int &i){
    t[++tot]=t[i];i=tot;
}

int update(int p,int v,int i,int l,int r){
    newnode(i);
    t[i].v+=v;
    if(l==r) return i;
    if(p<=mid) ls=update(p,v,ls,l,mid);
    else rs=update(p,v,rs,mid+1,r);
    return i;
}

int query(int ql,int qr,int vl,int vr,int l,int r){
    if(ql<=l&&r<=qr) return t[vr].v-t[vl].v;
    int res=0;
    if(ql<=mid) res+=query(ql,qr,t[vl].l,t[vr].l,l,mid);
    if(qr>mid) res+=query(ql,qr,t[vl].r,t[vr].r,mid+1,r);
    return res;
}

int n,m,a[N];

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) root[i]=update(a[i],a[i],root[i-1],1,1e9);
    cin>>m;
    while(m--){
        int ans=1,l,r;
        cin>>l>>r;
        while(1){
            int res=query(1,ans,root[l-1],root[r],1,1e9);
            if(res>=ans) ans=res+1;
            else break;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

P3293 [SCOI2016]美味

#include <bits/stdc++.h>
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;

const int N = 2e5+5;

struct node{
    int v,l,r;
} t[N<<5];
int tot,root[N];

int update(int p,int v,int i,int l,int r){
    t[++tot]=t[i];i=tot;
    t[i].v+=v;
    if(l==r) return i;
    if(p<=mid) ls=update(p,v,ls,l,mid);
    else rs=update(p,v,rs,mid+1,r);
    return i;
}

int query(int ql,int qr,int vl,int vr,int l,int r){
    if(qr<l||ql>r) return 0;
    if(ql<=l&&r<=qr) return t[vr].v-t[vl].v;
    int res=0;
    if(ql<=mid) res+=query(ql,qr,t[vl].l,t[vr].l,l,mid);
    if(qr>mid) res+=query(ql,qr,t[vl].r,t[vr].r,mid+1,r);
    return res;
}

int n,m,a[N];

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    int N = *max_element(a+1,a+n+1);
    for(int i=1;i<=n;i++) root[i]=update(a[i],1,root[i-1],0,N);
    while(m--){
        int b,x,l,r,ans=0;
        cin>>b>>x>>l>>r;
        for(int i=20;~i;i--){
            if(b&(1<<i)){
                if(!query(ans-x,ans-x+((1<<i)-1),root[l-1],root[r],0,N)) ans+=(1<<i);
            }
            else{
                if(query(ans-x+(1<<i),ans-x+((1<<(i+1))-1),root[l-1],root[r],0,N)) ans+=(1<<i);
            }
        }
        cout<<(ans^b)<<'\n';
    }
    return 0;
}

P2617 Dynamic Rankings

#include <bits/stdc++.h>
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;

const int N = 1e6+5;
int n,m;
int a[N];

struct node{
    int v,l,r;
} t[N<<5];
int tot,root[N];

void update(int p,int v,int &i,int l,int r){
    if(!i) i=(++tot);
    t[i].v+=v;
    if(l==r) return;
    if(p<=mid) update(p,v,ls,l,mid);
    else update(p,v,rs,mid+1,r);
}

inline int lowbit(int x){return x&(-x);}

void update(int p,int v){
    for(int i=p;i<=n;i+=lowbit(i)) update(a[p],-1,root[i],0,1e9);
    a[p]=v;
    for(int i=p;i<=n;i+=lowbit(i)) update(a[p],1,root[i],0,1e9);
}

int lr[N],rr[N],tl,tr;

inline void split(int l,int r){
    l--,tl=0,tr=0;
    for(int i=l;i;i-=lowbit(i)) lr[++tl]=root[i];
    for(int i=r;i;i-=lowbit(i)) rr[++tr]=root[i];
}

int kth(int k,int l,int r){
    if(l==r) return l;
    int siz=0;
    for(int i=1;i<=tl;i++) siz-=t[t[lr[i]].l].v;
    for(int i=1;i<=tr;i++) siz+=t[t[rr[i]].l].v;
    if(k<=siz){
        for(int i=1;i<=tl;i++) lr[i]=t[lr[i]].l;
        for(int i=1;i<=tr;i++) rr[i]=t[rr[i]].l;
        return kth(k,l,mid);
    }
    else{
        for(int i=1;i<=tl;i++) lr[i]=t[lr[i]].r;
        for(int i=1;i<=tr;i++) rr[i]=t[rr[i]].r;
        return kth(k-siz,mid+1,r);
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int j=1;j<=n;j++){
        cin>>a[j];
        for(int i=j;i<=n;i+=lowbit(i)) update(a[j],1,root[i],0,1e9);
    }
    while(m--){
        char op;int x,y,z;
        cin>>op>>x>>y;
        if(op=='Q'){
            cin>>z;
            split(x,y);cout<<kth(z,0,1e9)<<'\n';
        }
        else update(x,y);
    }
    return 0;
}

P3380 【模板】二逼平衡树（树套树）

#include <bits/stdc++.h>
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;

const int N = 1e5+5, INF = 2147483647;
int n,m;
int a[N],b[N],btot;

struct node{
    int v,l,r;
} t[N<<10];
int tot,root[N];

void update(int p,int v,int &i,int l,int r){
    if(!i) i=(++tot);
    t[i].v+=v;
    if(l==r) return;
    if(p<=mid) update(p,v,ls,l,mid);
    else update(p,v,rs,mid+1,r);
}

inline int lowbit(int x){return x&(-x);}

void update(int p,int v,bool clear=true){
    if(clear){for(int i=p;i<=n;i+=lowbit(i)) update(a[p],-1,root[i],1,btot);}
    a[p]=v;
    for(int i=p;i<=n;i+=lowbit(i)) update(a[p],1,root[i],1,btot);
}

int lr[N],rr[N],tl,tr;

inline void split(int l,int r){
    l--,tl=0,tr=0;
    for(int i=l;i;i-=lowbit(i)) lr[++tl]=root[i];
    for(int i=r;i;i-=lowbit(i)) rr[++tr]=root[i];
}

int kth(int k,int l=1,int r=btot){
    if(l==r) return l;
    int siz=0;
    for(int i=1;i<=tl;i++) siz-=t[t[lr[i]].l].v;
    for(int i=1;i<=tr;i++) siz+=t[t[rr[i]].l].v;
    if(k<=siz){
        for(int i=1;i<=tl;i++) lr[i]=t[lr[i]].l;
        for(int i=1;i<=tr;i++) rr[i]=t[rr[i]].l;
        return kth(k,l,mid);
    }
    else{
        for(int i=1;i<=tl;i++) lr[i]=t[lr[i]].r;
        for(int i=1;i<=tr;i++) rr[i]=t[rr[i]].r;
        return kth(k-siz,mid+1,r);
    }
}

int rnk(int v,int l=1,int r=btot){
    if(l==r) return 1;
    if(v<=mid){
        for(int i=1;i<=tl;i++) lr[i]=t[lr[i]].l;
        for(int i=1;i<=tr;i++) rr[i]=t[rr[i]].l;
        return rnk(v,l,mid);
    }
    else{
        int siz=0;
        for(int i=1;i<=tl;i++) siz-=t[t[lr[i]].l].v;
        for(int i=1;i<=tr;i++) siz+=t[t[rr[i]].l].v;
        for(int i=1;i<=tl;i++) lr[i]=t[lr[i]].r;
        for(int i=1;i<=tr;i++) rr[i]=t[rr[i]].r;
        return siz+rnk(v,mid+1,r);
    }
}

struct Query{
    int op,x,y,z;
} qs[N];

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int j=1;j<=n;j++){
        cin>>a[j];
        b[++btot]=a[j];
    }
    for(int j=1;j<=m;j++){
        cin>>qs[j].op>>qs[j].x>>qs[j].y;
        if(qs[j].op!=3){
            cin>>qs[j].z;
            if(qs[j].op!=2) b[++btot]=qs[j].z;
        }
        else b[++btot]=qs[j].y;
    }
    sort(b+1,b+btot+1);
    btot=unique(b+1,b+btot+1)-b-1;
    for(int i=1;i<=n;i++){
        int v=lower_bound(b+1,b+btot+1,a[i])-b;
        update(i,v,false);
    }
    for(int i=1;i<=m;i++){
        int op=qs[i].op,x=qs[i].x,y=qs[i].y,z=qs[i].z;
        if(op!=2&&op!=3) z=lower_bound(b+1,b+btot+1,z)-b;
        if(op==3) y=lower_bound(b+1,b+btot+1,y)-b;
        if(op==1){
            split(x,y);cout<<rnk(z)<<'\n';
        }
        if(op==2){
            split(x,y);cout<<b[kth(z)]<<'\n';
        }
        if(op==3) update(x,y);
        if(op==4){
            split(x,y);
            int pre=rnk(z);
            if(pre==1) cout<<(-INF)<<'\n';
            else{
                split(x,y);cout<<b[kth(pre-1)]<<'\n';
            }
        }
        if(op==5){
            split(x,y);
            int pre=rnk(z+1);
            split(x,y);
            int nxt=kth(pre);
            if(nxt!=z&&pre<=(y-x+1)) cout<<b[nxt]<<'\n';
            else cout<<INF<<'\n';
        }
    }
    return 0;
}