Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 贴个 splay ！！

Posted by wocha at 2013-10-18 22:30:08 on Problem 3481
```#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 ++) {
}
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 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();
return 0;
}
```

Followed by: