可持久化线段树

$主席树$

#include<cstdio>
#include<cstring>
#include<algorithm>
#define mid (l+r)/2
using namespace std;
const int N = 100010;
int n, q, m, cnt = 0;
int a[N], b[N], T[N];
int sum[N<<5], L[N<<5], R[N<<5];
int getid(int x){return lower_bound(b+1,b+1+m,x)-b;}
inline int build(int l, int r)
{
    int rt = ++ cnt;
    sum[rt] = 0;
    if (l < r){
        L[rt] = build(l, mid);
        R[rt] = build(mid+1, r);
    }
    return rt;
}
inline int update(int pre, int l, int r, int x)
{
    int rt = ++ cnt;
    L[rt] = L[pre]; R[rt] = R[pre]; sum[rt] = sum[pre]+1;
    if (l < r){
        if (x <= mid) L[rt] = update(L[pre], l, mid, x);
        else R[rt] = update(R[pre], mid+1, r, x);
    }
    return rt;
}
inline int query(int u, int v, int l, int r, int k)
{
    if (l >= r) return l;
    int x = sum[L[v]] - sum[L[u]];
    if (x >= k) return query(L[u], L[v], l, mid, k);
    else return query(R[u], R[v], mid+1, r, k-x);
}
int main()
{
     int t;scanf("%d",&t);
     while(t--){
          cnt=0;
             scanf("%d%d", &n, &q);
             for (int i = 1; i <= n; i ++){
                 scanf("%d", &a[i]);
                 b[i] = a[i];
             }
             sort(b+1, b+1+n);
             m = unique(b+1, b+1+n)-b-1;
             T[0] = build(1, m);
             for (int i = 1; i <= n; i ++){
                 T[i] = update(T[i-1], 1, m, getid(a[i]));
             }
             while (q --){
                 int x, y, z;
                 scanf("%d%d%d", &x, &y, &z);
                 printf("%d\n", b[query(T[x-1], T[y], 1, m, z)]);
             }
     }
}

$待修改主席树$
Dynamic Rankings

#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define scnaf scanf 
#define itn int
#define lson l,mid
#define rson mid+1,r
using namespace std;
const int o_o=6e4+5;
const int mod=1e9+7;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
int n,m,sz;
int Hash[o_o],a[o_o],cnt=0;
int root[o_o<<5],T[o_o],S[o_o];
int L[o_o<<5],R[o_o<<5],UR[o_o],UL[o_o];
struct node{
 int flag;
 int id,val;
 int l,r,k;
}Q[10005];
int getid(int x){return lower_bound(Hash+1,Hash+1+sz,x)-Hash;}
int build(int l,int r){
     int rt=++cnt;
     root[rt]=0;
     int mid=l+r>>1;
     if(l<r){
          L[rt]=build(lson);
          R[rt]=build(rson);
     }
     return rt;
}
int insert(int u,int l,int r,int pos,int val){
     int rt=++cnt;
     root[rt]=root[u]+val;
     L[rt]=L[u],R[rt]=R[u];
     int mid=l+r>>1;
     if(l>=r)return rt;
     if(l<r){
          if(pos<=mid)L[rt]=insert(L[u],lson,pos,val);
          else R[rt]=insert(R[u],rson,pos,val);
     }
     return rt;
}
void add(int x,int val){
     int id=getid(a[x]);
     for(int i=x;i<=n;i+=i&(-i)){
        S[i]=insert(S[i],1,sz,id,val);
     }
}
int getsum(int x,int flag){
     int res=0;
     for(int i=x;i;i&=i-1){
          if(flag)res+=root[L[UR[i]]];
          else res+=root[L[UL[i]]];
     }
     return res;
}
int query(int st,int ed,int u,int v,int l,int r,int k){
     int num=getsum(ed,true)-getsum(st,false)+root[L[v]]-root[L[u]];
     int mid=l+r>>1;
     if(l>=r)return l;
     if(k<=num){
          for(int i=ed;i;i&=i-1)UR[i]=L[UR[i]];
          for(int i=st;i;i&=i-1)UL[i]=L[UL[i]];
          return query(st,ed,L[u],L[v],lson,k);
     }else{
          for(int i=ed;i;i&=i-1)UR[i]=R[UR[i]];
          for(int i=st;i;i&=i-1)UL[i]=R[UL[i]];
          return query(st,ed,R[u],R[v],rson,k-num);
     }
}
int main(){
     int t;cin>>t;
     while(t--){
      cnt=0;
      scanf("%d%d",&n,&m);sz=n;
      for(int i=1;i<=n;i++)scnaf("%d",a+i),Hash[i]=a[i];
      for(int i=1;i<=m;i++){
           char str[2];
           scnaf("%s",str);
           if(str[0]=='Q'){
                Q[i].flag=true;
                scnaf("%d%d%d",&Q[i].l,&Q[i].r,&Q[i].k);
           }else{
                int pos,val;
                scnaf("%d%d",&pos,&val);
                Q[i].flag=false;
                Q[i].id=pos,Q[i].val=val;
                Hash[++sz]=val;
           }
      }
      sort(Hash+1,Hash+1+sz);
      sz=unique(Hash+1,Hash+1+sz)-Hash-1;
      T[0]=build(1,sz);
      for(int i=1;i<=n;i++)T[i]=insert(T[i-1],1,sz,getid(a[i]),1);
      for(int i=0;i<=n;i++)S[i]=T[0];
      for(int i=1;i<=m;i++){
                if(Q[i].flag){
                    for(int j=Q[i].r;j;j&=j-1)UR[j]=S[j];
                    for(int j=Q[i].l-1;j;j&=j-1)UL[j]=S[j];
                    printf("%d\n",Hash[query(Q[i].l-1,Q[i].r,T[Q[i].l-1],T[Q[i].r],1,sz,Q[i].k)]);
               }else{
                    add(Q[i].id,-1);
                    a[Q[i].id]=Q[i].val;
                    add(Q[i].id,1);
               }
          }
     }
}

$区间不同的数$
D-query

#include <bits/stdc++.h>
#define sc scanf
#define me(a,x) memset(a,x,sizeof(a))
#define itn int
#define fro for
using namespace std;
const int N=3e4+5;
int n,q,cnt=0;
int pos[1000005]={0};
int root[N<<6|1],L[N<<6|1],R[N<<6|1];
int tree[N<<6|1];
int build(int l,int r){
        int rt=++cnt;
        root[rt]=0;
        int mid=l+r>>1;
        if(l<r){
                L[rt]=build(l,mid);
                R[rt]=build(mid+1,r);
        }
        return rt;
}
int insert(int fa,int l,int r,int p,int val){
        int rt=++cnt;
        root[rt]=root[fa]+val;
        L[rt]=L[fa],R[rt]=R[fa];
        int mid=l+r>>1;
        if(l>=r)return rt;
        if(p<=mid)L[rt]=insert(L[fa],l,mid,p,val);
        else R[rt]=insert(R[fa],mid+1,r,p,val);
        return rt;
}
int Q(int rot,int limt,int l,int r){
        if(l>=limt)return root[rot];
        int mid=l+r>>1;
        int res=0;
        if(limt<=mid){
                res+=root[R[rot]];
                res+=Q(L[rot],limt,l,mid);
        }
        else res+=Q(R[rot],limt,mid+1,r);
        return res;
}
int main(){
        sc("%d",&n);
        tree[0]=build(1,n);
        for(itn i=1;i<=n;i++){
                int val;
                sc("%d",&val);
                if(pos[val]){
                        tree[i]=insert(tree[i-1],1,n,pos[val],-1);//将上一个位置减一
                        tree[i]=insert(tree[i],1,n,i,1);//这个位置加一不会有重复
                }
                else tree[i]=insert(tree[i-1],1,n,i,1);
                pos[val]=i;
        }
        sc("%d",&q);
        while(q--){
                int l,r;
                sc("%d%d",&l,&r);
                printf("%d\n",Q(tree[r],l,1,n));
        }
}