[关闭]
@zzzc18 2017-12-28T12:31:17.000000Z 字数 2156 阅读 996

BZOJ4546: codechef XRQRS

bzoj 可持久化数据结构


Description:

给定一个初始时为空的整数序列(元素由 开始标号)以及一些询问:
类型1:在数组后面就加入数字
类型2:在区间中找到y,最大化()。
类型3:删除数组最后 个元素。
类型4:在区间中,统计小于等于 的元素个数。
类型5:在区间中,找到第 小的数。


Solution:

因为要求“最大化()”,加上这是个带修改数据结构题,并且还要求别的东西,线性基(我不会)应该用不了,这时使用01Trie,可以解决这种问题,并且考虑一番后发现也可以解决类型4、5。
只要将01Trie可持久化,就可以求出区间的值。

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. const int MAXN = 520000+9;
  6. int tot_len;
  7. struct T{
  8. int ch[2];
  9. int size;
  10. int &operator [] (int x){
  11. return ch[x];
  12. }
  13. }tree[MAXN*20];
  14. int rt[MAXN];
  15. int cnt;
  16. int insert(int pre,int val,int bit_length){
  17. int now=++cnt;
  18. tree[now]=tree[pre];
  19. tree[now].size++;
  20. if(bit_length==-1)
  21. return now;
  22. bool tmp=val&(1<<bit_length);
  23. if(tmp)tree[now][1]=insert(tree[pre][1],val,bit_length-1);
  24. else tree[now][0]=insert(tree[pre][0],val,bit_length-1);
  25. return now;
  26. }
  27. int del(int x){
  28. tot_len-=x;
  29. }
  30. int max_xor(int pre,int now,int val){
  31. int re=0;
  32. for(int bit_length=19;bit_length>-1;bit_length--){
  33. bool tmp=val&(1<<bit_length);
  34. bool jud=tree[tree[now][tmp^1]].size-tree[tree[pre][tmp^1]].size;
  35. if(jud){
  36. re|=(tmp^1)*(1<<bit_length);
  37. pre=tree[pre][tmp^1];now=tree[now][tmp^1];
  38. }
  39. else{
  40. re|=(tmp)*(1<<bit_length);
  41. pre=tree[pre][tmp];now=tree[now][tmp];
  42. }
  43. }
  44. return re;
  45. }
  46. int smallers(int pre,int now,int val){
  47. int re=0;
  48. for(int bit_length=19;bit_length>-1;bit_length--){
  49. bool tmp=val&(1<<bit_length);
  50. if(tmp){
  51. re+=tree[tree[now][0]].size-tree[tree[pre][0]].size;
  52. }
  53. pre=tree[pre][tmp];now=tree[now][tmp];
  54. }
  55. //叶子节点
  56. re+=tree[now].size-tree[pre].size;
  57. return re;
  58. }
  59. int k_th(int pre,int now,int val){
  60. int re=0;
  61. for(int bit_length=19;bit_length>-1;bit_length--){
  62. int tmp=tree[tree[now][0]].size-tree[tree[pre][0]].size;
  63. if(val<=tmp){
  64. pre=tree[pre][0];now=tree[now][0];
  65. }
  66. else{
  67. val-=tmp;
  68. re|=(1<<bit_length);
  69. pre=tree[pre][1];now=tree[now][1];
  70. }
  71. }
  72. return re;
  73. }
  74. int main(){
  75. int kase;
  76. scanf("%d",&kase);
  77. while(kase--){
  78. int opt,x,l,r;
  79. scanf("%d",&opt);
  80. switch(opt){
  81. case 1:scanf("%d",&x);tot_len++;rt[tot_len]=insert(rt[tot_len-1],x,19);break;
  82. case 2:scanf("%d%d%d",&l,&r,&x);printf("%d\n",max_xor(rt[l-1],rt[r],x));break;
  83. case 3:scanf("%d",&x);del(x);break;
  84. case 4:scanf("%d%d%d",&l,&r,&x);printf("%d\n",smallers(rt[l-1],rt[r],x));break;
  85. default:scanf("%d%d%d",&l,&r,&x);printf("%d\n",k_th(rt[l-1],rt[r],x));break;
  86. }
  87. }
  88. return 0;
  89. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注