首页 > > 程序设计 > C/C++ >

bzoj4546 -- 可持久化字典树

2018-06-17 22:44:12来源：未知阅读 ()

可持久化字典树模板题。。。

把每个数转换成二进制建立字典树，按照下标建立可持久化字典树，存一下子树中点的个数就行了。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 inline char nc(){
 7     static char buf[100000],*p1=buf,*p2=buf;
 8     if(p1==p2){
 9         p2=(p1=buf)+fread(buf,1,100000,stdin);
10         if(p1==p2)return EOF;
11     }
12     return *p1++;
13 }
14 inline void Read(int& x){
15     char c=nc();
16     for(;c<'0'||c>'9';c=nc());
17     for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc());
18 }
19 #define N 520001
20 #define M 20
21 int i,j,k,n,m,Q,Rt[N],p[M],Sum[N*M],c[N*M][2],x,y,z,Num;
22 inline void Insert(int& x,int y){
23     int Tmp=++Num,Last=x;x=Tmp;
24     for(i=M-1;i>=0;i--){
25         bool d=y&p[i];
26         c[Tmp][0]=c[Last][0];c[Tmp][1]=c[Last][1];
27         Sum[Tmp]=Sum[Last]+1;
28         Last=c[Tmp][d];
29         c[Tmp][d]=++Num;Tmp=Num;
30     }
31     c[Tmp][0]=c[Last][0];c[Tmp][1]=c[Last][1];
32     Sum[Tmp]=Sum[Last]+1;
33 }
34 inline int Query_max(int x,int y,int z){
35     int Ans=0;
36     for(int i=M-1;i>=0;i--){
37         bool d=z&p[i];
38         if(Sum[c[y][d^1]]-Sum[c[x][d^1]]>0){
39             Ans+=d?0:p[i];
40             y=c[y][d^1];x=c[x][d^1];
41         }else y=c[y][d],x=c[x][d],Ans+=d?p[i]:0;
42     }
43     return Ans;
44 }
45 inline int Query_sum(int x,int y,int z){
46     int Ans=0;
47     for(int i=M-1;i>=0;i--){
48         bool d=z&p[i];
49         if(d)Ans+=Sum[c[y][0]]-Sum[c[x][0]];
50         if(Sum[c[y][d]]-Sum[c[x][d]]==0)return Ans;
51         x=c[x][d];y=c[y][d];
52     }
53     return Ans+Sum[y]-Sum[x];
54 }
55 inline int Query_kth(int x,int y,int z){
56     int Ans=0;
57     for(int i=M-1;i>=0;i--)
58     if(Sum[c[y][0]]-Sum[c[x][0]]>=z)x=c[x][0],y=c[y][0];
59     else{
60         Ans+=p[i];
61         z-=Sum[c[y][0]]-Sum[c[x][0]];
62         x=c[x][1];y=c[y][1];
63     }
64     return Ans;
65 }
66 int main(){
67     for(p[0]=i=1;i<M;i++)p[i]=p[i-1]<<1;
68     Read(Q);
69     while(Q--){
70         Read(k);
71         if(k==1)Read(x),n++,Rt[n]=Rt[n-1],Insert(Rt[n],x);else
72         if(k==2)Read(x),Read(y),Read(z),printf("%d\n",Query_max(Rt[x-1],Rt[y],z));else
73         if(k==3)Read(x),n-=x,Num=Rt[n+1]-1;else
74         if(k==4)Read(x),Read(y),Read(z),printf("%d\n",Query_sum(Rt[x-1],Rt[y],z));else
75         Read(x),Read(y),Read(z),printf("%d\n",Query_kth(Rt[x-1],Rt[y],z));
76     }
77     return 0;
78 }