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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 剑指offer27:按字典序打印出该字符串中字符的所有排列 2019-08-27
- 图论2——拓扑排序 2019-05-08
- bzoj3932 [ CQOI2015 ] --可持久化线段树 2018-06-27
- 增强版字典DictionaryEx 2018-06-18
- C#中服务端接受前端JSON字符串转换成字典集合 2018-06-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash