首页 > 代码库 > Splay!
Splay!
1 #include<cstdio> 2 #include<cstdlib> 3 const int mod =1000000007; 4 const int inf = ~0u>>2; 5 const int maxn = 200010; 6 int lim; 7 struct SplayTree { 8 19. int sz[maxn]; 9 20. int ch[maxn][2]; 10 21. int pre[maxn]; 11 22. int rt,top; 12 23. inline void up(int x){ 13 24. sz[x] = cnt[x] + sz[ ch[x][0] ] + sz[ ch[x][1] ]; 14 25. } 15 26. inline void Rotate(int x,int f){ 16 27. int y=pre[x]; 17 28. ch[y][!f] = ch[x][f]; 18 29. pre[ ch[x][f] ] = y; 19 30. pre[x] = pre[y]; 20 31. if(pre[x]) ch[ pre[y] ][ ch[pre[y]][1] == y ] =x; 21 32. ch[x][f] = y; 22 33. pre[y] = x; 23 34. up(y); 24 35. } 25 36. inline void Splay(int x,int goal){//将x旋转到goal的下面 26 37. while(pre[x] != goal){ 27 38. if(pre[pre[x]] == goal) Rotate(x , ch[pre[x]][0] == x); 28 39. else { 29 40. int y=pre[x],z=pre[y]; 30 41. int f = (ch[z][0]==y); 31 42. if(ch[y][f] == x) Rotate(x,!f),Rotate(x,f); 32 43. else Rotate(y,f),Rotate(x,f); 33 44. } 34 45. } 35 46. up(x); 36 47. if(goal==0) rt=x; 37 48. } 38 49. inline void RTO(int k,int goal){//将第k位数旋转到goal的下面 39 50. int x=rt; 40 51. while(sz[ ch[x][0] ] != k-1) { 41 52. if(k < sz[ ch[x][0] ]+1) x=ch[x][0]; 42 53. else { 43 54. k-=(sz[ ch[x][0] ]+1); 44 55. x = ch[x][1]; 45 56. } 46 57. } 47 58. Splay(x,goal); 48 59. } 49 60. inline void vist(int x){ 50 61. if(x){ 51 62. printf("结点%2d : 左儿子 %2d 右儿子 %2d %2d sz=%d\n",x,ch[x][0],ch[x][1],val[x],sz[x]); 52 63. vist(ch[x][0]); 53 64. vist(ch[x][1]); 54 65. } 55 66. } 56 67. inline void Newnode(int &x,int c){ 57 68. x=++top; 58 69. ch[x][0] = ch[x][1] = pre[x] = 0; 59 70. sz[x]=1; cnt[x]=1; 60 71. val[x] = c; 61 72. } 62 73. inline void init(){ 63 74. ans=0;type=-1; 64 75. ch[0][0]=ch[0][1]=pre[0]=sz[0]=0; 65 76. rt=top=0; cnt[0]=0; 66 77. Newnode(rt,-inf); 67 78. Newnode(ch[rt][1],inf); 68 79. pre[top]=rt; 69 80. sz[rt]=2; 70 81. } 71 82. inline void Insert(int &x,int key,int f){ 72 83. if(!x) { 73 84. Newnode(x,key); 74 85. pre[x]=f; 75 86. Splay(x,0); 76 87. return ; 77 88. } 78 89. if(key==val[x]){ 79 90. cnt[x]++; 80 91. sz[x]++; 81 92. return ; 82 93. }else if(key<val[x]) { 83 94. Insert(ch[x][0],key,x); 84 95. } else { 85 96. Insert(ch[x][1],key,x); 86 97. } 87 98. up(x); 88 99. } 89 100. void Del(){ 90 101. int t=rt; 91 102. if(ch[rt][1]) { 92 103. rt=ch[rt][1]; 93 104. RTO(1,0); 94 105. ch[rt][0]=ch[t][0]; 95 106. if(ch[rt][0]) pre[ch[rt][0]]=rt; 96 107. } 97 108. else rt=ch[rt][0]; 98 109. pre[rt]=0; 99 110. up(rt); 100 111. } 101 112. void findpre(int x,int key,int &ans){ 102 113. if(!x) return ; 103 114. if(val[x] <= key){ 104 115. ans=x; 105 116. findpre(ch[x][1],key,ans); 106 117. } else 107 118. findpre(ch[x][0],key,ans); 108 119. } 109 120. void findsucc(int x,int key,int &ans){ 110 121. if(!x) return ; 111 122. if(val[x]>=key) { 112 123. ans=x; 113 124. findsucc(ch[x][0],key,ans); 114 125. } else 115 126. findsucc(ch[x][1],key,ans); 116 127. } 117 128. void solve() { 118 129. int a,b,x,y; 119 130. scanf("%d%d",&a,&b); 120 131. if(a==type || sz[rt]==2){ 121 132. 122 133. Insert(rt,b,0),type=a; 123 134. //printf("type=%d\n",type); 124 135. } 125 136. else { 126 137. findpre(rt,b,x); 127 138. findsucc(rt,b,y); 128 139. if(abs(val[x]-b) <= abs(val[y]-b)) { 129 140. ans+=abs(val[x]-b); 130 141. ans%=mod; 131 142. Splay(x,0); 132 143. Del(); 133 144. } 134 145. else { 135 146. ans+=abs(val[y]-b); 136 147. ans%=mod; 137 148. Splay(y,0); 138 149. Del(); 139 150. } 140 151. } 141 152. //spt.vist(rt); 142 153. } 143 154. int cnt[maxn]; 144 155. int val[maxn]; 145 156. int type; 146 157. int ans; 147 158.}spt; 148 159.int main() 149 160.{ 150 161. int n; 151 162. scanf("%d",&n); 152 163. spt.init(); 153 164. while(n--) spt.solve(); 154 165. printf("%d\n",spt.ans); 155 166. return 0; 156 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。