[关闭]
@zzzc18 2017-12-29T09:48:02.000000Z 字数 2590 阅读 485

UVA-12538:Version Controlled IDE

Treap 可持久化数据结构 UVA


describtion.pdf17.5kB


使用可持久化的FHQ_Treap,维护各版本,注意一些题目里的细节就好。

  1. #include<ctime>
  2. #include<stack>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. using namespace std;
  8. const int MAXN = 1000000+9;
  9. int lastans;
  10. int n;
  11. struct PAIR{
  12. int left,right;
  13. PAIR(int _x=0,int _y=0):left(_x),right(_y){}
  14. };
  15. struct T{
  16. int ls,rs;
  17. char val;
  18. int size;
  19. int RD;
  20. }tree[MAXN*22];
  21. int rt[MAXN];
  22. int cnt;
  23. char BUF[MAXN];
  24. int Verson;
  25. int New_Node(char val=0){
  26. int now=++cnt;
  27. tree[now].val=val;
  28. tree[now].size=1;
  29. tree[now].RD=rand();
  30. return now;
  31. }
  32. int Copy_Node(int x){
  33. int now=New_Node();
  34. tree[now]=tree[x];
  35. return now;
  36. }
  37. void Clean(T &A){
  38. A.ls=A.rs=A.val=A.size=A.RD=0;
  39. }
  40. void update(int x){
  41. tree[x].size=tree[tree[x].ls].size+tree[tree[x].rs].size+1;
  42. }
  43. int Build(char *S,int &len){
  44. static stack<int> sta;
  45. while(!sta.empty())sta.pop();
  46. len=strlen(S);
  47. int from=cnt+1;
  48. for(int i=0;i<len;i++){
  49. int now=++cnt;
  50. tree[now].RD=rand();
  51. tree[now].val=S[i];
  52. tree[now].size=1;
  53. }
  54. int to=cnt;
  55. sta.push(0);
  56. Clean(tree[0]);
  57. int top;
  58. for(int i=from;i<=to;i++){
  59. while(true){
  60. top=sta.top();
  61. if(tree[top].RD<=tree[i].RD)
  62. break;
  63. update(top);
  64. sta.pop();
  65. }
  66. tree[i].ls=tree[top].rs;
  67. tree[top].rs=i;
  68. sta.push(i);
  69. }
  70. while(sta.size()>1){
  71. update(sta.top());
  72. sta.pop();
  73. }
  74. return tree[0].rs;
  75. }
  76. PAIR split(int k,int val){
  77. PAIR re;
  78. if(!k)return re;
  79. int now=Copy_Node(k);
  80. if(tree[tree[k].ls].size+1<=val){
  81. re=split(tree[k].rs,val-(tree[tree[k].ls].size+1));
  82. tree[now].rs=re.left;
  83. re.left=now;
  84. }
  85. else{
  86. re=split(tree[k].ls,val);
  87. tree[now].ls=re.right;
  88. re.right=now;
  89. }
  90. update(now);
  91. return re;
  92. }
  93. int merge(int x,int y){
  94. if(x==0 || y==0)
  95. return x+y;
  96. if(tree[x].RD<tree[y].RD){
  97. tree[x].rs=merge(tree[x].rs,y);
  98. update(x);
  99. return x;
  100. }
  101. else{
  102. tree[y].ls=merge(x,tree[y].ls);
  103. update(y);
  104. return y;
  105. }
  106. }
  107. void insert(int pre,int now,int loc){
  108. int len;
  109. int tmp=Build(BUF,len);
  110. PAIR rt1=split(rt[pre],loc);
  111. rt[now]=merge(rt1.left,merge(tmp,rt1.right));
  112. }
  113. void del(int pre,int now,int loc,int len){
  114. PAIR rt1=split(rt[pre],loc-1);
  115. PAIR rt2=split(rt1.right,len);
  116. rt[now]=merge(rt1.left,rt2.right);
  117. }
  118. void InOrder(int k){
  119. if(!k)return;
  120. InOrder(tree[k].ls);
  121. putchar(tree[k].val);
  122. if(tree[k].val=='c')lastans++;
  123. InOrder(tree[k].rs);
  124. }
  125. void OUTPUT(int pre,int loc,int len){
  126. PAIR rt1=split(rt[pre],loc-1);
  127. PAIR rt2=split(rt1.right,len);
  128. InOrder(rt2.left);
  129. puts("");
  130. rt[pre]=merge(rt1.left,merge(rt2.left,rt2.right));
  131. }
  132. int main(){
  133. srand(time(0));
  134. scanf("%d",&n);
  135. for(int i=1;i<=n;i++){
  136. int opt,loc,len,v;
  137. scanf("%d",&opt);
  138. switch(opt){
  139. case 1:scanf("%d",&loc);scanf("%s",BUF);
  140. loc-=lastans;
  141. Verson++;
  142. insert(Verson-1,Verson,loc);
  143. break;
  144. case 2:
  145. scanf("%d%d",&loc,&len);
  146. loc-=lastans;len-=lastans;
  147. Verson++;
  148. del(Verson-1,Verson,loc,len);
  149. break;
  150. default:
  151. scanf("%d%d%d",&v,&loc,&len);
  152. v-=lastans;loc-=lastans;len-=lastans;
  153. OUTPUT(v,loc,len);
  154. }
  155. }
  156. return 0;
  157. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注