主席树相关

裸主席树：

  1 #include<bits/stdc++.h>
  2 #define maxn 1008611
  3 #define maxm 10086
  4 using namespace std;
  5 
  6 template<size_t SIZE>
  7 struct MemoryPool{
  8     char buf[SIZE],*cur;
  9     
 10     MemoryPool():cur(buf){}
 11     
 12     inline void *alloc(const int size){
 13         if(cur==buf+SIZE) return malloc(size);
 14         else{
 15             char *p=cur;
 16             cur+=size;
 17             return p;
 18         }
 19     }
 20 };
 21 
 22 MemoryPool<(4+4+8+8+4)*maxn*10> pool;
 23 
 24 struct Chairman_Tree{
 25     struct Node{
 26         int l,r;
 27         Node *lc,*rc;
 28         int cnt;
 29         
 30         Node(const int l,const int r,Node *lc=NULL,Node *rc=NULL):l(l),r(r),lc(lc),rc(rc),cnt((lc?lc->cnt:0)+(rc?rc->cnt:0)){};
 31         Node(const int l,const int r,const int cnt):l(l),r(r),lc(NULL),rc(NULL),cnt(cnt){};
 32         
 33         inline void pushdown(){
 34             if(lc&&rc) return ;
 35             
 36             const int mid=(l+r)>>1;
 37             if(!lc) lc=new (pool.alloc(sizeof(Node))) Node(l,mid);
 38             if(!rc) rc=new (pool.alloc(sizeof(Node))) Node(mid+1,r);
 39         }
 40         
 41         Node *insert(const int val){
 42             if(val<l||val>r) return this;
 43             else if(val==l&&val==r) return new (pool.alloc(sizeof(Node))) Node(l,r,this->cnt+1);
 44             else{
 45                 const int mid=(l+r)>>1;
 46                 pushdown();
 47                 if(val<=mid) return new (pool.alloc(sizeof(Node))) Node(l,r,lc->insert(val),rc);
 48                 else return new (pool.alloc(sizeof(Node))) Node(l,r,lc,rc->insert(val));
 49             }
 50         }
 51         
 52         inline int rank() const {
 53             return lc?lc->cnt:0;
 54         } 
 55     }*root[maxn+1];
 56     
 57     int n;
 58     
 59     void build(const int a[],const int n){
 60         this->n=n;
 61         root[0]=new (pool.alloc(sizeof(Node))) Node(0,n-1);
 62         for(int i=1;i<=n;++i) root[i]=root[i-1]->insert(a[i-1]);
 63     }
 64     
 65     int query(const int l,const int r,int k){
 66         Node *L=root[l-1],*R=root[r];
 67         int min=0,max=n-1;
 68         while(min!=max){
 69             L->pushdown(),R->pushdown();
 70             int mid=(max+min)>>1,t=R->rank()-L->rank();
 71             if(k<=t) L=L->lc,R=R->lc,max=mid;
 72             else k-=t,L=L->rc,R=R->rc,min=mid+1;
 73         }
 74         return min;
 75     }
 76 }t;
 77 
 78 int n, m, a[maxn];
 79 
 80 int main() {
 81     scanf("%d %d", &n, &m);
 82     for (int i = 0; i < n; i++) scanf("%d", &a[i]);
 83 
 84     static int set[maxn];
 85     copy(a, a + n, set);
 86     sort(set, set + n);
 87     int *end = unique(set, set + n);
 88     for (int i = 0; i < n; i++) a[i] = lower_bound(set, end, a[i]) - set;
 89 
 90     t.build(a, n);
 91 
 92     for (int i = 0; i < m; i++) {
 93         int l, r, k;
 94         scanf("%d %d %d", &l, &r, &k);
 95         int ans = t.query(l, r, k);
 96         printf("%d
", set[ans]);
 97     }
 98 
 99     return 0;
100 }

可持久化数组：

 1 #include<cstdio>
 2 #define MAXN 1000005
 3 
 4 int base[MAXN];
 5 
 6 template<typename T,size_t maxn>
 7 struct Chairman_Tree{
 8     enum Relation{
 9         L=0,R=1
10     };
11     
12     int root[maxn];
13     int ch[maxn][2];
14     T val[maxn];
15     int index=0;
16     
17     inline void build(int &o,const T a[],const int &l,const int &r){
18         o=++index;
19         
20         if(l==r){
21             val[o]=a[l];
22             return;
23         }
24         
25         const int mid=(l+r)>>1;
26         build(ch[o][L],a,l,mid);
27         build(ch[o][R],a,mid+1,r);
28     }
29     
30     inline void modify(int &o,const int &pre,const int &l,const int &r,const int &k,const T &v){
31         o=++index;
32         
33         ch[o][L]=ch[pre][L],ch[o][R]=ch[pre][R],val[o]=val[pre];
34         
35         if(l==r){
36             val[o]=v;
37             return;
38         }
39         const int mid=(l+r)>>1;
40         if(k<=mid) modify(ch[o][L],ch[pre][L],l,mid,k,v);
41         else modify(ch[o][R],ch[pre][R],mid+1,r,k,v);
42     }
43     
44     inline int query(const int &o,const int &l,const int &r,const int &k){
45         if(l==r) return val[o];
46         const int mid=(l+r)>>1;
47         if(k<=mid) return query(ch[o][L],l,mid,k);
48         else return query(ch[o][R],mid+1,r,k);
49     }
50 };
51 
52 Chairman_Tree<int,MAXN*20> CT;
53 
54 int main(){
55     register int n,m;
56     scanf("%d%d",&n,&m);
57     
58     for(register int i=1;i<=n;++i) scanf("%d",&base[i]);
59     CT.build(CT.root[0],base,1,n);
60     
61     register int pre,opt,x,y;
62     for(register int i=1;i<=m;++i){
63         scanf("%d%d%d",&pre,&opt,&x);
64         if(opt==1){
65             scanf("%d",&y);
66             CT.modify(CT.root[i],CT.root[pre],1,n,x,y);
67         }else{
68             printf("%d
",CT.query(CT.root[pre],1,n,x));
69             CT.root[i]=CT.root[pre];
70         }
71     }
72     return 0;
73 }

主席树统计区间数种数：

  1 #pragma G++ optimize (2)
  2 #include<cstdio>
  3 #include<map>
  4 #define N 100001
  5 
  6 template<typename T>
  7 inline void read(T &x){
  8   char ch;while((ch=getchar()),(ch>'9'||ch<'0'));
  9   x=ch-'0';while((ch=getchar()),(ch>='0'&&ch<='9')) x=x*10+ch-'0';
 10 }
 11 
 12 template<size_t maxn>
 13 struct Chairman_Tree{
 14     enum Relation{
 15         L=0,R=1
 16     };
 17     
 18     int root[maxn*20],index;
 19     int ch[maxn*20][2],val[maxn*20];
 20     
 21     Chairman_Tree():index(0){
 22         //memset(root,0,sizeof root);
 23         //memset(ch,0,sizeof ch);
 24         //memset(val,0,sizeof val);
 25     }
 26     
 27     inline void pushup(const int &o){
 28         val[o]=val[ch[o][L]]+val[ch[o][R]];
 29     }
 30     
 31     int build(const int &l,const int &r){
 32         int o=index++;
 33         
 34         if(l==r){
 35             val[o]=0;
 36             return o;
 37         }
 38         
 39         const int mid=(l+r)>>1;
 40         ch[o][L]=build(l,mid);
 41         ch[o][R]=build(mid+1,r);
 42         
 43         return o;
 44     }
 45     
 46     int update(const int pre,const int &l,const int &r,const int &pos,const int &v){
 47         int o=index++;
 48         
 49         ch[o][L]=ch[pre][L],ch[o][R]=ch[pre][R];
 50         val[o]=val[pre];
 51         
 52         if(l==pos&&r==pos){
 53             val[o]+=v;
 54             return o;
 55         }
 56         
 57         const int mid=(l+r)>>1;
 58         if(pos<=mid) ch[o][L]=update(ch[pre][L],l,mid,pos,v);
 59         else ch[o][R]=update(ch[pre][R],mid+1,r,pos,v);
 60         
 61         pushup(o);
 62         return o;
 63     }
 64     
 65     int query(const int &o,const int &l,const int &r,const int &pos){
 66         if(l==r) return val[o];
 67         
 68         const int mid=(l+r)>>1;
 69         if(pos<=mid) return val[ch[o][R]]+query(ch[o][L],l,mid,pos);
 70         else return query(ch[o][R],mid+1,r,pos);
 71     }
 72 };
 73 
 74 Chairman_Tree<N> CT;
 75 std::map<int,int> mp;
 76 int b[N];
 77 
 78 int main(){
 79     register int n,m,x,y;
 80     read(n);
 81     
 82     for(register int i=1;i<=n;++i) read(b[i]);
 83     CT.root[0]=CT.build(1,n);
 84     
 85     for(register int i=1;i<=n;++i){
 86         if(mp.find(b[i])==mp.end())
 87             CT.root[i]=CT.update(CT.root[i-1],1,n,i,1);
 88         else{
 89             int tmp=CT.update(CT.root[i-1],1,n,mp[b[i]],-1);
 90             CT.root[i]=CT.update(tmp,1,n,i,1);
 91         }
 92         mp[b[i]]=i;
 93     }
 94     
 95     read(m);
 96     for(register int i=0;i<m;++i){
 97         read(x),read(y);
 98         printf("%d
",CT.query(CT.root[y],1,n,x));
 99     }
100 }

树状数组套主席树（可修改主席树）：

 1 #include<cstdio>
 2 #include<algorithm>
 3 
 4 #define lowbit(x) (x&-x)
 5 #define N 10005
 6 
 7 int n,m;
 8 int a[N],b[N<<1|1];
 9 
10 template<size_t maxn>
11 struct Modifiable_CT{
12     enum Realtion{
13         L=0,R=1
14     };
15     
16     int sz,totx,toty,totn;
17     int root[maxn];
18     int xx[maxn],yy[maxn];
19     int ch[maxn*600][2],size[maxn*600];
20     
21     void ins(int &o,const int &l,const int &r,const int pre,const int &k,const int &v){
22         o=++sz;
23         
24         size[o]=size[pre]+v;
25         ch[o][L]=ch[pre][L],ch[o][R]=ch[pre][R];
26         
27         if(l==r) return;
28         const int mid=(l+r)>>1;
29         if(k<=mid) ins(ch[o][L],l,mid,ch[pre][L],k,v);
30         else ins(ch[o][R],mid+1,r,ch[pre][R],k,v);
31     }
32     
33     void modify(const int &x,const int &v){
34         int k=std::lower_bound(b+1,b+totn+1,a[x])-b;
35         for(int i=x;i<=n;i+=lowbit(i)) ins(root[i],1,totn,root[i],k,v);
36     }
37     
38     int query(const int &l,const int &r,const int &k){
39         if(l==r) return l;
40         
41         int sum=0;
42         const int mid=(l+r)>>1;
43         
44         for(int i=1;i<=totx;++i) sum-=size[ch[xx[i]][L]];
45         for(int i=1;i<=toty;++i) sum+=size[ch[yy[i]][L]];
46         
47         if(k<=sum){
48             for(int i=1;i<=totx;++i) xx[i]=ch[xx[i]][L];
49             for(int i=1;i<=toty;++i) yy[i]=ch[yy[i]][L];
50             return query(l,mid,k);
51         }else{
52             for(int i=1;i<=totx;++i) xx[i]=ch[xx[i]][R];
53             for(int i=1;i<=toty;++i) yy[i]=ch[yy[i]][R];
54             return query(mid+1,r,k-sum);
55         }
56     }
57 };
58 
59 Modifiable_CT<N> MCT;
60 
61 
62 
63 int ca[N],cb[N],cc[N];
64 inline int read(){
65     int f=1,x=0;char ch;
66     do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
67     do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
68     return f*x;
69 }
70 
71 int main(){
72     register char s[20];
73     n=read();m=read();
74     for(register int i=1;i<=n;i++)a[i]=read(),b[++MCT.totn]=a[i];
75     for(register int i=1;i<=m;i++){
76         scanf("%s",s);ca[i]=read();cb[i]=read();
77         if(s[0]=='Q')cc[i]=read();else b[++MCT.totn]=cb[i];
78     }
79     std::sort(b+1,b+MCT.totn+1);
80     MCT.totn=std::unique(b+1,b+MCT.totn+1)-b-1;
81     for(register int i=1;i<=n;i++) MCT.modify(i,1);
82     for(register int i=1;i<=m;i++){
83         if(cc[i]){
84             MCT.totx=MCT.toty=0;
85             for(register int j=ca[i]-1;j;j-=lowbit(j))MCT.xx[++MCT.totx]=MCT.root[j];
86             for(register int j=cb[i];j;j-=lowbit(j))MCT.yy[++MCT.toty]=MCT.root[j];
87             printf("%d
",b[MCT.query(1,MCT.totn,cc[i])]);
88         }
89         else{MCT.modify(ca[i],-1);a[ca[i]]=cb[i];MCT.modify(ca[i],1);}
90     }
91 }