前言

今天机房莫名掀起了一股学习主席树的浪潮，然而这对于早几天接触主席树的我，岂不是个XXX的好机会= =

然而我是一个正直的人，所以就把这些鬼东西扔出来，顺便给自己做个小结

静态主席树

顾名思义，就是静态的，不带修改的主席树

很简单的东西，用前缀和维护的，可以查询区间$k$小值的数据结构，然而只有理解了，才可以灵活运用，乃至将其作用推广

懒得写教程了（其实只是不想码字= =）（那不还是懒吗）

当时太年轻，打的太丑= =

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 //#define mem(x) memset((x),0,sizeof(x)) 7 inline int read(){ 8     int sum(0); 9     char ch(getchar());10     for(;ch<'0'||ch>'9';ch=getchar());11     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());12     return sum;13 }14 int T;15 int n,m;16 int a[100005],num[100005];17 int cnt,size;18 int rt[2000005],sum[2000005],lch[2000005],rch[2000005];19 inline void clear(){20 //    mem(a),mem(num),mem(rt),mem(sum),mem(lch),mem(rch);21     cnt=size=n=m=0;22 }23 inline void build(int &x,int l,int r){24     x=++cnt;25     sum[x]=0;26     if(l==r){27         lch[x]=rch[x]=0;28         return;29     }30     int mid((l+r)>>1);31     build(lch[x],l,mid);32     build(rch[x],mid+1,r);33 }34 inline void update(int &x,int las,int pos,int l,int r){35     x=++cnt;36     lch[x]=lch[las];37     rch[x]=rch[las];38     sum[x]=sum[las]+1;39     if(l==r)40         return;41     int mid((l+r)>>1);42     if(pos<=mid)43         update(lch[x],lch[las],pos,l,mid);44     else45         update(rch[x],rch[las],pos,mid+1,r);46 }47 inline int query(int ll,int rr,int l,int r,int k){48     if(l==r)49         return l;50     int mid((l+r)>>1);51     int cnt(sum[lch[rr]]-sum[lch[ll]]);52     if(k<=cnt)53         return query(lch[ll],lch[rr],l,mid,k);54     return query(rch[ll],rch[rr],mid+1,r,k-cnt);55 }56 int main(){57     T=read();58     while(T--){59         clear();60         n=read(),m=read();61         for(int i=1;i<=n;++i)62             num[i]=a[i]=read();63         sort(num+1,num+n+1);64         size=unique(num+1,num+n+1)-num-1;65         for(int i=1;i<=n;++i)66             a[i]=lower_bound(num+1,num+size+1,a[i])-num;67         build(rt[0],1,size);68         for(int i=1;i<=n;++i)69             update(rt[i],rt[i-1],a[i],1,size);70         for(int i=1;i<=m;++i){71             int l(read()),r(read()),k(read());72             int ans(query(rt[l-1],rt[r],1,size,k));73             printf("%d\n",num[ans]);74         }75     }76 }
         
        
       
      

树上建主席树，二分查即可

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 using namespace std;  6 inline int read(){  7     int sum(0);  8     char ch(getchar());  9     for(;ch<'0'||ch>'9';ch=getchar()); 10     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar()); 11     return sum; 12 } 13 struct edge{ 14     int e; 15     edge *n; 16 }a[200005],*pre[100005]; 17 int tot; 18 inline void insert(int s,int e){ 19     a[++tot].e=e; 20     a[tot].n=pre[s]; 21     pre[s]=&a[tot]; 22 } 23 int timee; 24 int dep[100005],fa[100005][20],l[100005],r[100005],pos[100005]; 25 int n,m; 26 int cnt,size; 27 int v[100005],num[100005]; 28 int rt[100005],lch[2000005],rch[2000005],sum[2000005]; 29 inline void dfs(int u){ 30     l[u]=++timee; 31     pos[timee]=u; 32     for(int i=1;(1<
          
           <=dep[u];++i) 33         fa[u][i]=fa[fa[u][i-1]][i-1]; 34     for(edge *i=pre[u];i;i=i->n){ 35         int e(i->e); 36         if(e!=fa[u][0]){ 37             fa[e][0]=u; 38             dep[e]=dep[u]+1; 39             dfs(e); 40         } 41     } 42     r[u]=timee; 43 } 44 inline int lca(int x,int y){ 45     if(dep[x]
           
            0;++i) 49 if(delta&(1<
            
             =0;--i) 56 if(fa[x][i]!=fa[y][i]) 57 x=fa[x][i],y=fa[y][i]; 58 return fa[x][0]; 59 } 60 inline void build(int &x,int l,int r){ 61 x=++cnt; 62 sum[x]=0; 63 if(l==r) 64 return; 65 int mid((l+r)>>1); 66 build(lch[x],l,mid); 67 build(rch[x],mid+1,r); 68 } 69 inline void update(int &x,int las,int pos,int l,int r){ 70 x=++cnt; 71 lch[x]=lch[las]; 72 rch[x]=rch[las]; 73 sum[x]=sum[las]+1; 74 if(l==r) 75 return; 76 int mid((l+r)>>1); 77 if(pos<=mid) 78 update(lch[x],lch[las],pos,l,mid); 79 else 80 update(rch[x],rch[las],pos,mid+1,r); 81 } 82 inline int query(int x,int y,int k){ 83 int a(x),b(y),c(lca(x,y)),d(fa[c][0]); 84 a=rt[l[a]],b=rt[l[b]],c=rt[l[c]],d=rt[l[d]]; 85 int l(1),r(size); 86 while(l
             
              >1); 88 int tmp(sum[lch[a]]+sum[lch[b]]-sum[lch[c]]-sum[lch[d]]); 89 if(k<=tmp) 90 r=mid,a=lch[a],b=lch[b],c=lch[c],d=lch[d]; 91 else 92 k-=tmp,l=mid+1,a=rch[a],b=rch[b],c=rch[c],d=rch[d]; 93 } 94 return num[l]; 95 } 96 int ans; 97 int main(){ 98 memset(pre,NULL,sizeof(pre)); 99 n=read(),m=read();100 for(int i=1;i<=n;++i)101 num[i]=v[i]=read();102 for(int i=1;i
             
            
           
          
         
        
       
      

[Poi2014]Couriers

太水，没写博客，基本上就是板子

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 inline int read(){ 6     int sum(0); 7     char ch(getchar()); 8     for(;ch<'0'||ch>'9';ch=getchar()); 9     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());10     return sum;11 }12 int n,m;13 int cnt;14 int a[500005];15 int rt[15000005],sum[15000005],lch[15000005],rch[15000005];16 inline void build(int &x,int l,int r){17     x=++cnt;18     sum[x]=0;19     if(l==r)20         return;21     int mid((l+r)>>1);22     build(lch[x],l,mid);23     build(rch[x],mid+1,r);24 }25 inline void update(int &x,int las,int pos,int l,int r){26     x=++cnt;27     lch[x]=lch[las];28     rch[x]=rch[las];29     sum[x]=sum[las]+1;30     if(l==r)31         return;32     int mid((l+r)>>1);33     if(pos<=mid)34         update(lch[x],lch[las],pos,l,mid);35     else36         update(rch[x],rch[las],pos,mid+1,r);37 }38 inline int query(int x,int y,int l,int r,int k){39     if(l==r){40         if(sum[y]-sum[x]<=k)41             return 0;42         return l;43     }44     int mid((l+r)>>1);45     if(sum[lch[y]]-sum[lch[x]]>k)46         return query(lch[x],lch[y],l,mid,k);47     if(sum[rch[y]]-sum[rch[x]]>k)48         return query(rch[x],rch[y],mid+1,r,k);49     return 0;50 }51 int main(){52     n=read(),m=read();53     for(int i=1;i<=n;++i)54         a[i]=read();55     build(rt[0],1,n);56     for(int i=1;i<=n;++i)57         update(rt[i],rt[i-1],a[i],1,n);58     while(m--){59         int l(read()),r(read());60         printf("%d\n",query(rt[l-1],rt[r],1,n,(r-l+1)>>1));61     }62 }
        
       
      

[BZOJ3653]谈笑风生

这道题没来得及写博客，以深度建树，维护$size$的和，$x$，$y$的答案=$size[x]\times min(deep[x],y)+dfs$序在$l[x]$到$r[x]$之间且深度在$deep[x]+1$到$deep[x]+k$之间的$size$和（话说这道题扔这个板块合适吗= =）

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 inline int read(){ 7     int sum(0); 8     char ch(getchar()); 9     for(;ch<'0'||ch>'9';ch=getchar());10     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());11     return sum;12 }13 struct edge{14     int e;15     edge *n;16 }a[600005],*pre[300005];17 int tot;18 inline void insert(int s,int e){19     a[++tot].e=e;20     a[tot].n=pre[s];21     pre[s]=&a[tot];22 }23 typedef long long L;24 int n,q;25 int timee;26 int l[300005],r[300005],pos[300005],size[300005],fa[300005],dep[300005];27 inline void dfs(int u){28     l[u]=++timee;29     pos[timee]=u;30     size[u]=1;31     for(edge *i=pre[u];i;i=i->n){32         int e(i->e);33         if(e!=fa[u]){34             fa[e]=u;35             dep[e]=dep[u]+1;36             dfs(e);37             size[u]+=size[e];38         }39     }40     r[u]=timee;41 }42 int mx,cnt;43 int rt[300005],lch[6000005],rch[6000005];44 L sum[6000005];45 inline void update(int &x,int las,int pos,int w,int l,int r){46     x=++cnt;47     lch[x]=lch[las];48     rch[x]=rch[las];49     sum[x]=sum[las]+w;50     if(l==r)51         return;52     int mid((l+r)>>1);53     if(pos<=mid)54         update(lch[x],lch[las],pos,w,l,mid);55     else56         update(rch[x],rch[las],pos,w,mid+1,r);57 }58 inline L query(int x,int y,int ll,int rr,int l,int r){59     if(ll<=l&&r<=rr)60         return sum[y]-sum[x];61     int mid((l+r)>>1);62     L ret(0);63     if(ll<=mid)64         ret+=query(lch[x],lch[y],ll,rr,l,mid);65     if(mid
         
        
       
      

 动态主席树（树状数组套主席树）

实际上没有啥，就是把维护前缀和的工具改为的树状数组式的而已，具体的只要理解的主席树与树状数组，其余的就很好打了

板子题

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 using namespace std;  6 inline int read(){  7     int sum(0);  8     char ch(getchar());  9     for(;ch<'0'||ch>'9';ch=getchar()); 10     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar()); 11     return sum; 12 } 13 int n,m; 14 int tot,size,cnt; 15 int v[10005],num[20005],has[20005]; 16 int rt[10005],sum[2500005],lch[2500005],rch[2500005]; 17 int A[10005],B[10005],K[10005]; 18 bool flag[10005]; 19 int a,b,L[30],R[30]; 20 char op[2]; 21 inline int lowbit(int x){ 22     return x&-x; 23 } 24 inline int find(int x){ 25     int l(1),r(size),mid; 26     while(l<=r){ 27         mid=(l+r)>>1; 28         if(has[mid]
          
           >1); 44     if(pos<=mid) 45         update(lch[x],lch[las],pos,w,l,mid); 46     else 47         update(rch[x],rch[las],pos,w,mid+1,r); 48 } 49 inline int query(int l,int r,int k){ 50     if(l==r) 51         return l; 52     int suml(0),sumr(0),mid((l+r)>>1); 53     for(int i=1;i<=a;++i)suml+=sum[lch[L[i]]]; 54     for(int i=1;i<=b;++i)sumr+=sum[lch[R[i]]]; 55     if(sumr-suml>=k){ 56         for(int i=1;i<=a;++i)L[i]=lch[L[i]]; 57         for(int i=1;i<=b;++i)R[i]=lch[R[i]]; 58         return query(l,mid,k); 59     } 60     else{ 61         for(int i=1;i<=a;++i)L[i]=rch[L[i]]; 62         for(int i=1;i<=b;++i)R[i]=rch[R[i]]; 63         return query(mid+1,r,k-(sumr-suml)); 64     } 65 } 66 int main(){ 67     n=read(),m=read(); 68     for(int i=1;i<=n;++i){ 69         v[i]=read(); 70         num[++tot]=v[i]; 71     } 72     for(int i=1;i<=m;++i){ 73         scanf("%s",op); 74         if(op[0]=='Q'){ 75             flag[i]=1; 76             A[i]=read(); 77             B[i]=read(); 78             K[i]=read(); 79         } 80         else{ 81             A[i]=read(); 82             B[i]=read(); 83             num[++tot]=B[i]; 84         } 85     } 86     sort(num+1,num+tot+1); 87     has[++size]=num[1]; 88     for(int i=2;i<=tot;++i) 89         if(num[i]!=num[i-1]) 90             has[++size]=num[i]; 91     for(int i=1;i<=n;++i){ 92         int tmp(find(v[i])); 93         for(int j=i;j<=n;j+=lowbit(j)) 94             update(rt[j],rt[j],tmp,1,1,size); 95     } 96     for(int i=1;i<=m;++i){ 97         if(flag[i]){ 98             a=b=0; 99             --A[i];100             for(int j=A[i];j>0;j-=lowbit(j))101                 L[++a]=rt[j];102             for(int j=B[i];j>0;j-=lowbit(j))103                 R[++b]=rt[j];104             printf("%d\n",has[query(1,size,K[i])]);105         }106         else{107             int tmp(find(v[A[i]]));108             for(int j=A[i];j<=n;j+=lowbit(j))109                 update(rt[j],rt[j],tmp,-1,1,size);110             v[A[i]]=B[i];111             tmp=find(B[i]);112             for(int j=A[i];j<=n;j+=lowbit(j))113                 update(rt[j],rt[j],tmp,1,1,size);114         }115     }116 }
          
         
        
       
      

[CQOI2015]任务查询系统

其实是静态的，但是要用树状数组套一下，所以就扔在这里了

差分一下，瞎XX乱搞就行了

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 using namespace std;  6 typedef long long L;  7 inline L read(){  8     L sum(0),f(1);  9     char ch(getchar()); 10     for(;ch<'0'||ch>'9';ch=getchar()) 11         if(ch=='-') 12             f=-1; 13     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar()); 14     return sum*f; 15 } 16 int m,n; 17 int cnt,tot; 18 int q[100005],top; 19 int s[100005],e[100005],p[100005],num[100005]; 20 int rt[100005],size[20000005],lch[20000005],rch[20000005]; 21 L sum[20000005]; 22 L ans(1),x,a,b,c,k; 23 inline int lowbit(int x){ 24     return x&-x; 25 } 26 inline int insert(int x,int val,int f){ 27     if(!x) 28         x=++cnt; 29     size[x]+=f; 30     sum[x]+=f*num[val]; 31     int tmp(x); 32     int l(1),r(m); 33     while(l
          
           >1); 35         if(val<=mid){ 36             r=mid; 37             if(!lch[x]) 38                 lch[x]=++cnt; 39             x=lch[x]; 40             size[x]+=f; 41             sum[x]+=f*num[val]; 42         } 43         else{ 44             l=mid+1; 45             if(!rch[x]) 46                 rch[x]=++cnt; 47             x=rch[x]; 48             size[x]+=f; 49             sum[x]+=f*num[val]; 50         } 51     } 52     return tmp; 53 } 54 inline void update(int x,int val,int f){ 55     for(int i=x;i<=n;i+=lowbit(i)) 56         rt[i]=insert(rt[i],val,f); 57 } 58 inline L query(int x,int k){ 59     L ret(0),tot(0); 60     top=0; 61     for(int i=x;i>0;i-=lowbit(i)){ 62         q[++top]=rt[i]; 63         tot+=size[rt[i]]; 64         ret+=sum[rt[i]]; 65     } 66     if(k>tot) 67         return ret; 68     ret=0; 69     int l(1),r(m); 70     while(l
           
            >1),tmp(0); 72 for(int i=1;i<=top;++i) 73 tmp+=size[lch[q[i]]]; 74 if(tmp
           
          
         
        
       
      

树剖上乱搞

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
        
       
      

突然发现根本没做几道题，我好弱啊QAQ

可。。。可。。。可持久化？

真正的可持久化到来，有关历史版本的修改与查询，实际上理解了主席树的修改操作，这个就变得异常的简单起来

[COGS 2554][福利]可持久化线段树

单点修改的板子题，没啥好说的

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 inline int read(){ 6     int sum(0); 7     char ch(getchar()); 8     for(;ch<'0'||ch>'9';ch=getchar()); 9     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());10     return sum;11 }12 int n,q,t(1);13 int a[10005];14 int cnt;15 int rt[100005],lch[20000005],rch[20000005],mx[20000005];16 inline void pushup(int i){17     mx[i]=max(mx[lch[i]],mx[rch[i]]);18 }19 inline void build(int &x,int l,int r){20     x=++cnt;21     if(l==r){22         mx[x]=a[l];23         return;24     }25     int mid((l+r)>>1);26     build(lch[x],l,mid);27     build(rch[x],mid+1,r);28     pushup(x);29 }30 inline void update(int &x,int las,int pos,int w,int l,int r){31     x=++cnt;32     lch[x]=lch[las];33     rch[x]=rch[las];34     mx[x]=mx[las];35     if(l==r){36         mx[x]=w;37         return;38     }39     int mid((l+r)>>1);40     if(pos<=mid)41         update(lch[x],lch[las],pos,w,l,mid);42     else43         update(rch[x],rch[las],pos,w,mid+1,r);44     pushup(x);45 }46 inline int query(int x,int ll,int rr,int l,int r){47     if(ll==l&&r==rr)48         return mx[x];49     int mid((l+r)>>1);50     if(rr<=mid)51         return query(lch[x],ll,rr,l,mid);52     if(mid
        
       
      

可持久化线段树区间修改的板子题

1 #include
      
         2 #include
       
          3 #include
        
           4 using namespace std;  5 typedef long long L;  6 inline int read(){  7     int sum(0),f(1);  8     char ch(getchar());  9     for(;ch<'0'||ch>'9';ch=getchar()) 10         if(ch=='-') 11             f=-1; 12     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar()); 13     return sum*f; 14 } 15 int n,m,t,cnt; 16 int v[100005]; 17 int rt[100005],lch[4000005],rch[4000005]; 18 L sum[4000005],add[4000005]; 19 char op[2]; 20 inline int build(int l,int r){ 21     int x(++cnt); 22     add[x]=0; 23     if(l==r){ 24         sum[x]=v[l]; 25         lch[x]=rch[x]=0; 26 //        cout<<"pos "<
         
          <<" "<
          
           <<' '<
           
            <<" "<
            
             <<' '<
             
              <
              
               >1); 30 lch[x]=build(l,mid); 31 // cout<<"left child"<
               
                <<" "<
                
                 <<' '<
                 
                  <
                  
                   >1))+add[rch[x]]*(len>>1); 42 } 43 inline int update(int rt,int ll,int rr,L w,int l,int r){ 44 int newrt(++cnt); 45 add[newrt]=add[rt]; 46 if(ll<=l&&r<=rr){ 47 sum[newrt]=sum[rt]; 48 add[newrt]=add[rt]+w; 49 lch[newrt]=lch[rt]; 50 rch[newrt]=rch[rt]; 51 return newrt; 52 } 53 int mid((l+r)>>1); 54 if(ll<=mid) 55 lch[newrt]=update(lch[rt],ll,rr,w,l,mid); 56 else 57 lch[newrt]=lch[rt]; 58 if(mid
                   
                    >1); 70 L ret(0); 71 if(ll<=mid) 72 ret+=query(lch[rt],ll,rr,l,mid,add[rt]+add1); 73 if(mid
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      

真正做过的难题出现！

树剖+可持久化线段树区间修改+线段树上维护等差数列（其实没多难，我太弱而已= =）

1 #include
      
         2 #include
       
          3 #include
        
           4 using namespace std;  5 typedef long long L;  6 inline L read(){  7     L sum(0),f(1);  8     char ch(getchar());  9     for(;ch<'0'||ch>'9';ch=getchar()) 10         if(ch=='-') 11             f=-1; 12     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar()); 13     return sum*f; 14 } 15 struct edge{ 16     int e; 17     edge *n; 18 }a[200005],*pre[100005]; 19 int to; 20 inline void insert(int s,int e){ 21     a[++to].e=e; 22     a[to].n=pre[s]; 23     pre[s]=&a[to]; 24 } 25 int n,m,now,tot; 26 char op[2]; 27 int dep[100005],size[100005],fa[100005],son[100005]; 28 inline void dfs1(int u){ 29     size[u]=1; 30     son[u]=0; 31     dep[u]=dep[fa[u]]+1; 32     for(edge *i=pre[u];i;i=i->n){ 33         int e(i->e); 34         if(e!=fa[u]){ 35             fa[e]=u; 36             dfs1(e); 37             size[u]+=size[e]; 38             if(size[e]>size[son[u]]) 39                 son[u]=e; 40         } 41     } 42 } 43 int timee; 44 int id[100005],top[100005]; 45 inline void dfs2(int u,int rt){ 46     top[u]=rt; 47     id[u]=++timee; 48     if(son[u]) 49         dfs2(son[u],rt); 50     for(edge *i=pre[u];i;i=i->n){ 51         int e(i->e); 52         if(e!=son[u]&&e!=fa[u]) 53             dfs2(e,e); 54     } 55 } 56 inline int lca(int x,int y){ 57     while(top[x]^top[y]){ 58         if(dep[top[x]]
         
          >1); 82     if(rr<=mid) 83         update(lch[x],lch[las],ll,rr,sx,gc,l,mid); 84     else 85         if(mid
          
           >1); 97     if(rr<=mid) 98         return ret+query(lch[x],ll,rr,l,mid); 99     if(mid
           
            dep[y])132 swap(x,y);133 ret+=query(rt[now],id[x],id[y],1,n);134 return ret;135 }136 int main(){137 memset(pre,NULL,sizeof(pre));138 n=read(),m=read();139 for(int i=1;i
           
          
         
        
       
      

REAL 小结？

反正主席树这东西用处不少，就是联赛貌似用不到，所以只能期望自己能撑过联赛，自己也要加油啊