Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- inline int myRandom() {
- return (rand() << 16) ^ rand();
- }
- const int BUF = 1005000;
- struct node {
- int val;
- int cnt, pr;
- node *lf, *rg;
- node(){
- val = 0;
- pr = cnt = 0;
- lf = rg = 0;
- }
- };
- typedef node* tree;
- int szbuf;
- node buf[BUF];
- tree allocate(int val){
- assert(szbuf < BUF);
- tree res = &buf[szbuf++];
- res->val = val;
- res->pr = myRandom();
- res->cnt = 1;
- res->lf = 0;
- res->rg = 0;
- return res;
- }
- inline int getCnt(tree t){
- return t ? (t->cnt) : 0;
- }
- inline void update(tree t){
- if(!t)
- return;
- t->cnt = getCnt(t->lf) + getCnt(t->rg) + 1;
- }
- inline void push(tree t){
- // push data here...
- }
- void split(tree t, int x, tree& lf, tree& rg){
- if(!t){
- lf = rg = 0;
- return;
- }
- push(t);
- int pos = getCnt(t->lf);
- if(pos < x){
- split(t->rg, x - pos - 1, t->rg, rg);
- lf = t;
- }else{
- split(t->lf, x, lf, t->lf);
- rg = t;
- }
- update(lf);
- update(rg);
- }
- tree merge(tree lf, tree rg){
- if(!lf || !rg)
- return lf ? lf : rg;
- push(lf);
- push(rg);
- tree t;
- if(lf->pr > rg->pr){
- t = lf;
- lf->rg = merge(lf->rg, rg);
- }else{
- t = rg;
- rg->lf = merge(lf, rg->lf);
- }
- update(t);
- return t;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement