fork download
  1.  
  2. using namespace std;
  3. struct Node
  4. { int sz, label, f;
  5. Node *p, *ch[2];
  6. Node(int v=0) { p = ch[0] = ch[1] = 0;label=v;f=1; }
  7. };
  8. typedef Node* pnode;
  9. int sz(pnode t){
  10. return t?t->sz:0;
  11. }
  12. void update(Node *x){
  13. if (!x)return ;
  14. x->sz=x->f+sz(x->ch[0])+sz(x->ch[1]);
  15. }
  16. void rot(Node *x){
  17. Node *y, *z;
  18. y = x->p, z = y->p;
  19. int xp=(x==y->ch[0])?0:1,yp=(z)?((y==z->ch[0])?0:1):-1;
  20. if ((y->ch[xp]=x->ch[1^xp]))y->ch[xp]->p=y;
  21. x->ch[1^xp] = y, y->p = x;
  22. if ((x->p=z))z->ch[yp]=x;
  23. update(y);
  24. }
  25.  
  26. void splay(Node *x){
  27. if (!x)return ;
  28. while (x->p)rot(x);
  29. update(x);
  30. }
  31. void join (pnode & c,Node *L , Node *R){
  32. if (!L||!R){ c=(!L)?R:L,update(c);return ;}
  33. c=L;
  34. while (c->ch[1])c=c->ch[1];
  35. splay(c);c->ch[1]=R;if (R) R->p=c;
  36. update(c);
  37. }
  38. Node * find (Node * T ,int k,Node *p=0){
  39. if (!T)return p;
  40. return (T->label==k)?T:(T->label>k)?find(T->ch[0],k,T):find(T->ch[1],k,T);
  41. }
  42. void split (pnode T,pnode & L,pnode & R ,int x){
  43. if (!T){ L=R=NULL;return ;}
  44. T=find(T,x);splay(T);
  45. if (T->label>x)L=T->ch[0],T->ch[0]=0,R=T;
  46. else R=T->ch[1],T->ch[1]=0,L=T;
  47. if (L)L->p=0;if (R)R->p=0;
  48. update(L);update(R);
  49. }
  50.  
  51. void insert(pnode & T,int x){
  52. pnode n=new Node(x);
  53. pnode l=0,r=0;
  54. if (T) {
  55. T=find(T,x);splay(T);
  56. if (T->label==x)T->f++;
  57. else{
  58. split(T, l, r, x),n->ch[0] = l,n->ch[1] = r;
  59. if (l)l->p = n;
  60. if (r)r->p = n;
  61. T=n;
  62. }
  63. }
  64. if (!T)T=n;
  65. update(T);
  66. }
  67. void erase (pnode & n,int k){
  68. if (!n)return ;
  69. n=find(n,k);splay(n);
  70. if (n->label==k){
  71. n->f--;
  72. if (!n->f){
  73. if (n->ch[0])n->ch[0]->p=0;
  74. if (n->ch[1])n->ch[1]->p=0;
  75. join(n,n->ch[1],n->ch[0]);
  76. }
  77. }
  78. }
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
prog.cpp: In function ‘void split(pnode, Node*&, Node*&, int)’:
prog.cpp:43:18: error: ‘NULL’ was not declared in this scope
     if (!T){ L=R=NULL;return ;}
                  ^~~~
stdout
Standard output is empty