#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define keyTree (ch[ ch[root][1] ][0])
const int maxn = 1222222;
const int inf = 0x3f3f3f3f;
struct node {
 int id,priority;
};
struct SplayTree{
	int sz[maxn];
	int ch[maxn][2];
	int pre[maxn];
	int root , top1 , top2;
	int ss[maxn] , que[maxn];
	inline void Rotate(int x,int f) {
		int y = pre[x];
		ch[y][!f] = ch[x][f];
		pre[ ch[x][f] ] = y;
		pre[x] = pre[y];
		if(pre[x]) ch[ pre[y] ][ ch[pre[y]][1] == y ] = x;
		ch[x][f] = y;
		pre[y] = x;
		push_up(y);
	}
	inline void Splay(int x,int goal) {
		while(pre[x] != goal) {
			if(pre[pre[x]] == goal) {
				Rotate(x , ch[pre[x]][0] == x);
			} else {
				int y = pre[x] , z = pre[y];
				int f = (ch[z][0] == y);
				if(ch[y][f] == x) {
					Rotate(x , !f) , Rotate(x , f);
				} else {
					Rotate(y , f) , Rotate(x , f);
				}
			}
		}
		push_up(x);
		if(goal == 0) root = x;
	}
	inline void RotateTo(int k,int goal) {
		int x = root;
		while(sz[ ch[x][0] ] != k) {
			if(k < sz[ ch[x][0] ]) {
				x = ch[x][0];
			} else {
				k -= (sz[ ch[x][0] ] + 1);
				x = ch[x][1];
			}
		}
		Splay(x,goal);
	}
	inline void erase(int x) {
		int father = pre[x];
		int head = 0 , tail = 0;
		for (que[tail++] = x ; head < tail ; head ++) {
			ss[top2 ++] = que[head];
			if(ch[ que[head] ][0]) que[tail++] = ch[ que[head] ][0];
			if(ch[ que[head] ][1]) que[tail++] = ch[ que[head] ][1];
		}
		ch[ father ][ ch[father][1] == x ] = 0;
		push_up(father);
	}
	int NewNode(node c) {
        int x;
		if (top2) x = ss[--top2];
		else x = ++top1;
		ch[x][0] = ch[x][1] = pre[x] = 0;
		sz[x] = 1;    client[x] = c;
        return x;
	}
	inline void push_up(int x) {
		sz[x] = 1 + sz[ ch[x][0] ] + sz[ ch[x][1] ];
	}

	inline void init() {
		ch[0][0] = ch[0][1] = pre[0] = sz[0] = 0;
		root = top1 = 0;
		node c;
		c.priority = -inf;
		c.id= 0;
		int x = NewNode(c);
		root=1;
		c.priority = inf;
		x = NewNode(c);
		pre[x] = root;
		ch[root][1]=x;
		sz[root] = 2;
        num = 0;
		push_up(ch[root][1]);
		push_up(root);
	}
    int Insert(int rt,node c) {
     if(c.priority<client[rt].priority) {
        if(ch[rt][0]) {
          return  Insert(ch[rt][0],c);
        }  else {
            int x = NewNode(c);
            pre[x]=rt;   ch[rt][0]=x;
            push_up(rt);
            return x;
        }
     }
     if(c.priority>client[rt].priority){
        if(ch[rt][1]) return Insert( ch[rt][1] ,c);
        else {
            int x = NewNode(c);
            pre[x] = rt;   ch[rt][1] = x;  push_up(rt);
            return x;
        }
     }
    }
    int readIn(){
     int op  ;
     node c;   scanf("%d",&op);
     if(op==0) return 0;
     if(op==1)    {
        scanf("%d%d",&c.id,&c.priority);
        int xx=Insert(root,c);  Splay(xx,0);
        num++;
     }
     if(op==2)  {
        if(num>=1)  {
        RotateTo(num-1,0);
        RotateTo(num+1,root);
        printf("%d\n",client[keyTree].id);
        erase(keyTree);
        num--;
        } else puts("0"), root=1;
     }
     if(op==3)  {
        if(num>=1)  {
        RotateTo(0,0);  RotateTo(2,root);
        printf("%d\n",client[keyTree].id);
        erase(keyTree);
        num--;
        } else puts("0"),root=1;
     }
     return 1;
    }
    node client[maxn];
    int num;
}spt;
int main() {
    spt.init();
	while(spt.readIn());
	return 0;
}

• Re:贴个 splay ！！ (3795) yyzg02 2019-12-29 20:37:34