[关闭]
@zzzc18 2017-06-23T09:35:40.000000Z 字数 4915 阅读 634

树套树 Treap+Segment_Tree

线段树 Treap


二逼平衡树

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:

1.查询k在区间内的排名

2.查询区间内排名为k的值

3.修改某一位值上的数值

4.查询k在区间内的前驱(前驱定义为严格小于x,且最大的数,若不存在输出-2147483647)

5.查询k在区间内的后继(后继定义为严格大于x,且最小的数,若不存在输出2147483647)

总之上面的询问就是树套树的套路了


洛谷上的数据很铁,时间也紧,不加奇技淫巧的优化本方法过不了(正解往往是CDQ分治和zky线段树等)

我就(zhi)说(hui)Treap+线段树


询问是区间内的,所以线段树在外层,Treap在内层

每一个线段树节点是一个Treap //参见Build函数

由于每个节点单独一个Treap开不下,Treap的空间要统一使用,但每个Treap有自己的root和size //见node

操作1:和线段树的查询一样,只不过在区间内要用Treap去找比查询值小的数的个数,求和后再加1

操作2:看代码,通过二分找到其值究竟是多少

操作3:线段树单点修改,在经过节点的Treap删去原来的值,加入新值

操作4,5:凡是满足条件的线段树区间内都用Treap把前驱后继求一下,前驱取最大值,后继取最小值(注意返回值:若没有找到,前驱返回-INF,后即返回INF)

讲完了。。。


  1. #prag\
  2. ma GCC optimize("O3")
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<algorithm>
  6. #define MAXN 1200009
  7. #define INF 0x7fffffff
  8. using namespace std;
  9. int n,m;
  10. int a[MAXN];
  11. struct T_T{
  12. int ls,rs,rd,sz,num,val;
  13. }node[MAXN];
  14. int size;
  15. class Tree_Heap{
  16. public:
  17. int root,ans;
  18. int m;
  19. void update(int x){
  20. node[x].sz=node[node[x].ls].sz+node[node[x].rs].sz+node[x].num;
  21. }
  22. void rotate_l(int &k){
  23. int y=node[k].rs;
  24. node[k].rs=node[y].ls;
  25. node[y].ls=k;
  26. node[y].sz=node[k].sz;
  27. update(k);
  28. k=y;
  29. }
  30. void rotate_r(int &k){
  31. int y=node[k].ls;
  32. node[k].ls=node[y].rs;
  33. node[y].rs=k;
  34. node[y].sz=node[k].sz;
  35. update(k);
  36. k=y;
  37. }
  38. void insert(int &k,int v){
  39. if(k==0){
  40. size++;k=size;node[k].val=v;
  41. node[k].sz=node[k].num=1;node[k].rd=rand();
  42. return;
  43. }
  44. node[k].sz++;
  45. if(node[k].val==v){
  46. node[k].num++;
  47. }
  48. else if(v>node[k].val){
  49. insert(node[k].rs,v);
  50. if(node[node[k].rs].rd<node[k].rd)rotate_l(k);
  51. }
  52. else{
  53. insert(node[k].ls,v);
  54. if(node[node[k].ls].rd<node[k].rd)rotate_r(k);
  55. }
  56. }
  57. void del(int &k,int v){
  58. if(k==0)return;
  59. if(node[k].val==v){
  60. if(node[k].num>1){
  61. node[k].sz--;node[k].num--;
  62. return;
  63. }
  64. if(node[k].ls==0 || node[k].rs==0)k=node[k].ls+node[k].rs;
  65. else if(node[node[k].ls].rd<node[node[k].rs].rd){
  66. rotate_r(k);
  67. del(k,v);
  68. }
  69. else{
  70. rotate_l(k);
  71. del(k,v);
  72. }
  73. }
  74. else if(node[k].val<v){
  75. node[k].sz--;
  76. del(node[k].rs,v);
  77. }
  78. else{
  79. node[k].sz--;
  80. del(node[k].ls,v);
  81. }
  82. }
  83. int n2r(int x){
  84. int u=root;int re=1;
  85. while(u){
  86. if(node[u].val<x){
  87. re+=node[node[u].ls].sz+node[u].num;
  88. u=node[u].rs;
  89. }
  90. else
  91. u=node[u].ls;
  92. }
  93. return re;
  94. }
  95. int r2n(const int &k,int x){
  96. if(k==0) return 0;
  97. if(x<=node[node[k].ls].sz) return r2n(node[k].ls,x);
  98. else if(x>node[node[k].ls].sz+node[k].num)return r2n(node[k].rs,x-node[k].num-node[node[k].ls].sz);
  99. else return node[k].val;
  100. }
  101. void pred(const int &k,int x){
  102. if(k==0)return;
  103. if(node[k].val<x){
  104. ans=k;
  105. pred(node[k].rs,x);
  106. }
  107. else{
  108. pred(node[k].ls,x);
  109. }
  110. }
  111. void succ(const int &k,int x){
  112. if(k==0)return;
  113. if(node[k].val>x){
  114. ans=k;
  115. succ(node[k].ls,x);
  116. }
  117. else
  118. succ(node[k].rs,x);
  119. }
  120. int Succ(int x){
  121. ans=0;
  122. succ(root,x);
  123. return ans?node[ans].val:INF;
  124. }
  125. int Pred(int x){
  126. ans=0;
  127. pred(root,x);
  128. return ans?node[ans].val:-INF;
  129. }
  130. void INS(int x){
  131. insert(root,x);
  132. }
  133. void DEL(int x){
  134. del(root,x);
  135. }
  136. int N2R(int x){
  137. return n2r(x);
  138. }
  139. void DEBUG(int k){
  140. if(k==0)
  141. return;
  142. DEBUG(node[k].ls);
  143. printf("DEBUG-------%d\n",node[k].val);
  144. DEBUG(node[k].rs);
  145. }
  146. };
  147. class Segment_Tree_For_Treap{
  148. public:
  149. Tree_Heap Treap[MAXN];
  150. int cnt;
  151. struct T_T_T{
  152. int ls,rs,left_range,right_range;
  153. }tree[MAXN];
  154. int rank(int k,int l,int r,int v){
  155. if(l<=tree[k].left_range && tree[k].right_range<=r){
  156. int t=Treap[k].N2R(v)-1;
  157. return t;
  158. }
  159. int re=0;
  160. int mid=(tree[k].left_range+tree[k].right_range)>>1;
  161. if(l<=mid) re+=rank(tree[k].ls,l,r,v);
  162. if(mid+1<=r) re+=rank(tree[k].rs,l,r,v);
  163. return re;
  164. }
  165. int Build(int l,int r){
  166. int now=++cnt;
  167. tree[now].left_range=l;tree[now].right_range=r;
  168. if(l==r){
  169. Treap[now].INS(a[l]);
  170. //Treap[now].DEBUG(Treap[now].root);
  171. //printf("\n\n");
  172. return now;
  173. }
  174. for(int i=l;i<=r;i++){
  175. Treap[now].INS(a[i]);
  176. //Treap[now].DEBUG(Treap[now].root);
  177. //printf("\n\n");
  178. }
  179. int mid=(l+r)>>1;
  180. tree[now].ls=Build(l,mid);
  181. tree[now].rs=Build(mid+1,r);
  182. return now;
  183. }
  184. void change(int k,int pos,int v){
  185. Treap[k].DEL(a[pos]);
  186. Treap[k].INS(v);
  187. //Treap[k].DEBUG(Treap[k].root);
  188. //printf("\n\n");
  189. if(tree[k].left_range==tree[k].right_range){
  190. a[pos]=v;
  191. return;
  192. }
  193. int mid=(tree[k].left_range+tree[k].right_range)>>1;
  194. if(pos<=mid)change(tree[k].ls,pos,v);
  195. else change(tree[k].rs,pos,v);
  196. }
  197. int Pred(int k,int l,int r,int v){
  198. if(l<=tree[k].left_range && tree[k].right_range<=r){
  199. return Treap[k].Pred(v);
  200. }
  201. int s=-INF;
  202. int mid=(tree[k].left_range+tree[k].right_range)>>1;
  203. if(l<=mid) s=max(s,Pred(tree[k].ls,l,r,v));
  204. if(mid+1<=r) s=max(s,Pred(tree[k].rs,l,r,v));
  205. return s;
  206. }
  207. int Succ(int k,int l,int r,int v){
  208. if(l<=tree[k].left_range && tree[k].right_range<=r){
  209. return Treap[k].Succ(v);
  210. }
  211. int s=INF;
  212. int mid=(tree[k].left_range+tree[k].right_range)>>1;
  213. if(l<=mid) s=min(s,Succ(tree[k].ls,l,r,v));
  214. if(mid+1<=r) s=min(s,Succ(tree[k].rs,l,r,v));
  215. return s;
  216. }
  217. int n2r(int l,int r,int val){
  218. return rank(1,l,r,val)+1;
  219. }
  220. int r2n(int k,int l,int r,int v){
  221. int ll=0,rr=100000000;
  222. while(ll<=rr){
  223. int mid=(ll+rr)>>1;
  224. if(n2r(l,r,mid)>v) rr=mid-1;
  225. else ll=mid+1;
  226. }
  227. return rr;
  228. }
  229. }Seg;
  230. int zz(){
  231. scanf("%d%d",&n,&m);
  232. int i;
  233. for(i=1;i<=n;i++)
  234. scanf("%d",&a[i]);
  235. Seg.Build(1,n);
  236. for(i=1;i<=m;i++){
  237. int opt,l,r,k,pos;
  238. scanf("%d",&opt);
  239. if(opt==1){
  240. scanf("%d%d%d",&l,&r,&k);
  241. printf("%d\n",Seg.n2r(l,r,k));
  242. }
  243. if(opt==2){
  244. scanf("%d%d%d",&l,&r,&k);
  245. printf("%d\n",Seg.r2n(1,l,r,k));
  246. }
  247. if(opt==3){
  248. scanf("%d%d",&pos,&k);
  249. Seg.change(1,pos,k);
  250. }
  251. if(opt==4){
  252. scanf("%d%d%d",&l,&r,&k);
  253. printf("%d\n",Seg.Pred(1,l,r,k));
  254. }
  255. if(opt==5){
  256. scanf("%d%d%d",&l,&r,&k);
  257. printf("%d\n",Seg.Succ(1,l,r,k));
  258. }
  259. }
  260. return 0;
  261. }
  262. int zzz=zz();
  263. int main(){
  264. ;
  265. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注