fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
Standard output is empty
https://ideone.com/qRJcLv
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!