[关闭]
@zzzc18 2017-06-18T10:24:37.000000Z 字数 1715 阅读 617

bzoj1588 Treap

bzoj Treap


传送门

这题读了久才读懂,其实就是插入一个数之后查它的前驱和后继,取更小的,另外如果先前已经插入过一个数,波动就是为0;

使用Treap实现。

  1. #include<cmath>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<algorithm>
  5. #define MAXN 50000
  6. #define inf 0x7fffffff
  7. using namespace std;
  8. struct T{
  9. int ls,rs,sz,num,val,rd;
  10. T(){
  11. val=inf;
  12. }
  13. }tree[MAXN];
  14. int ans,size,root;
  15. int n,tot;
  16. int x;
  17. int Find(const int &k,int x){
  18. if(tree[k].val==x)return k;
  19. if(tree[k].val<x)
  20. return Find(tree[k].rs,x);
  21. else
  22. return Find(tree[k].ls,x);
  23. }
  24. void update(int x){
  25. tree[x].sz=tree[tree[x].ls].sz+tree[tree[x].rs].sz+tree[x].num;
  26. }
  27. void rotate_l(int &k){
  28. int y=tree[k].rs;
  29. tree[k].rs=tree[y].ls;
  30. tree[y].ls=k;
  31. tree[y].sz=tree[k].sz;
  32. update(k);
  33. k=y;
  34. }
  35. void rotate_r(int &k){
  36. int y=tree[k].ls;
  37. tree[k].ls=tree[y].rs;
  38. tree[y].rs=k;
  39. tree[y].sz=tree[k].sz;
  40. update(k);
  41. k=y;
  42. }
  43. void insert(int &k,int v){
  44. if(k==0){
  45. size++;k=size;
  46. tree[k].sz=tree[k].num=1;
  47. tree[k].val=v;
  48. tree[k].rd=rand();
  49. return;
  50. }
  51. tree[k].sz++;
  52. if(tree[k].val==v){
  53. tree[k].num++;
  54. }
  55. else if(tree[k].val<v){
  56. insert(tree[k].rs,v);
  57. if(tree[tree[k].rs].rd<tree[k].rd)rotate_l(k);
  58. }
  59. else{
  60. insert(tree[k].ls,v);
  61. if(tree[tree[k].ls].rd<tree[k].rd)rotate_r(k);
  62. }
  63. }
  64. void pred(const int &k,int v){
  65. if(k==0)return;
  66. if(tree[k].val<v){
  67. ans=k;
  68. pred(tree[k].rs,v);
  69. }
  70. else
  71. pred(tree[k].ls,v);
  72. }
  73. void succ(const int &k,int v){
  74. if(k==0)return;
  75. if(tree[k].val>v){
  76. ans=k;
  77. succ(tree[k].ls,v);
  78. }
  79. else
  80. succ(tree[k].rs,v);
  81. }
  82. int main(){
  83. freopen("bzoj.in","r",stdin);
  84. freopen("out.out","w",stdout);
  85. scanf("%d",&n);
  86. int i;
  87. scanf("%d",&x);
  88. insert(root,x);
  89. tot=x;
  90. for(i=2;i<=n;i++){
  91. scanf("%d",&x);
  92. insert(root,x);
  93. int loc=Find(root,x);
  94. if(tree[loc].num>1){
  95. ans=0;
  96. }
  97. else{
  98. int s,p;
  99. ans=0;
  100. pred(root,x);
  101. if(tree[ans].val!=inf)
  102. p=abs(x-tree[ans].val);
  103. else
  104. p=inf;
  105. ans=0;
  106. succ(root,x);
  107. if(tree[ans].val!=inf)
  108. s=abs(x-tree[ans].val);
  109. else
  110. s=inf;
  111. ans=min(p,s);
  112. }
  113. tot+=ans;
  114. printf("ans: %d\n",ans);
  115. }
  116. printf("%d\n",tot);
  117. return 0;
  118. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注