fork download
  1. //Pranet Verma
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. namespace Splay
  5. {
  6. typedef struct Node* pnode;
  7. pnode null;
  8. struct Node
  9. {
  10. int val,mx,sz;
  11. pnode c[2],p;
  12. };
  13. bool getDir(pnode p,pnode x)
  14. {
  15. return p->c[1]==x;
  16. }
  17. void setLink(pnode x,pnode y,int d)
  18. {
  19. x->c[d]=y;
  20. y->p=x;
  21. }
  22. void update(pnode u)
  23. {
  24. u->sz=1+u->c[0]->sz+u->c[1]->sz;
  25. u->mx=max(u->val,max(u->c[0]->mx,u->c[1]->mx));
  26. }
  27. void rotate(pnode y,bool d)
  28. {
  29. pnode x=y->c[d],z=y->p;
  30. setLink(y,x->c[d^1],d);
  31. setLink(x,y,d^1);
  32. setLink(z,x,getDir(z,y));
  33. update(x);update(y);
  34. }
  35. void splay(pnode x)
  36. {
  37. while(x->p!=null)
  38. {
  39. pnode y=x->p,z=y->p;
  40. int dy=getDir(y,x),dz=getDir(z,y);
  41. if(z==null)
  42. rotate(y,dy);
  43. else if(dy==dz)
  44. rotate(z,dz),rotate(y,dy);
  45. else
  46. rotate(y,dy),rotate(z,dz);
  47. }
  48. }
  49. pnode get(pnode u,int key,int add)
  50. {
  51. while(1)
  52. {
  53. int rank=1+add+u->c[0]->sz;
  54. if(rank==key)
  55. {
  56. splay(u);
  57. return u;
  58. }
  59. else if(rank<key)
  60. {
  61. add=rank;
  62. u=u->c[1];
  63. }
  64. else
  65. u=u->c[0];
  66. }
  67. }
  68. void split(pnode u,pnode &l,pnode &r,int key,int add)
  69. {
  70. if(key==add)
  71. {
  72. l=null;
  73. r=u;
  74. }
  75. else
  76. {
  77. l=get(u,key,add);
  78. r=l->c[1];
  79. l->c[1]=r->p=null;
  80. update(l);
  81. }
  82. }
  83. int query(pnode u,int l,int r,int x,int y)
  84. {
  85. if(x>r || y<l)
  86. return -1e9-9;
  87. if(x<=l && r<=y)
  88. return u->mx;
  89. int rank=l+u->c[0]->sz;
  90. int ret=-1e9-9;
  91. if(x<=rank && rank<=y)
  92. ret=u->val;
  93. ret=max(ret,query(u->c[0],l,rank-1,x,y));
  94. ret=max(ret,query(u->c[1],rank+1,r,x,y));
  95. return ret;
  96. }
  97. Node buff[100005];
  98. pnode ptr=buff;
  99. pnode newNode()
  100. {
  101. return ++ptr;
  102. }
  103. }
  104. using namespace Splay;
  105. int main()
  106. {
  107. null= newNode();
  108. null->val=null->mx=-1e9-9;
  109. null->sz=0;
  110. null->c[0]=null->c[1]=null->p=null;
  111. int m;
  112. scanf("%d\n",&m);
  113. pnode root=null;
  114. while(m--)
  115. {
  116. char ty;
  117. int x,y;
  118. scanf("%c %d %d\n",&ty,&x,&y);
  119. if(ty=='A')
  120. {
  121. pnode a,b;
  122. split(root,a,b,y-1,0);
  123. root=newNode();
  124. root->val=root->mx=x;
  125. root->sz=1;
  126. root->c[0]=a;
  127. root->c[1]=b;
  128. root->p=null;
  129. update(root);
  130. a->p=b->p=root;
  131. }
  132. else if(ty=='Q')
  133. {
  134. printf("%d\n",query(root,1,root->sz,x,y));
  135. }
  136. else
  137. assert(0);
  138. }
  139. }
Runtime error #stdin #stdout #stderr 0s 5808KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
prog: prog.cpp:137: int main(): Assertion `0' failed.