poj 3481 Double Que splay

Double Que
Time Limit:1000 MS
 
メモリLimit:65536 K
Total Submissions:10244
 
Acceepted:4651
Description
The new founded Balkan Investment Group Bank(BIG-Bank)opened a new office in BBucharet、equipped d with a moden copppputinininprovided by IBM Romani、and using moden in in information technolologies.Aspclininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininを選択します.he or she receives a positive integer prority P.One of the inventions of the young mage of the bank shed the bank shed the software enginese of the serving system.Thy proposed to break the tradion by Sometimetimetalthe system will receive the follwing types of request:
0
The system needs to stop serving
1 K P
Add client K to the waiting list with prority P
2
Serve the client with the highest prority and drop hir or her from the waiting list
3
Serve the client with the lowest prority and drop hir or her from the waiting list
Your task is to help the software enginer of the bank by writing a program to implement the requested serving policy.
Input
Each LINE of the input contains one of the possible requests;only the last line contains the stop-request(code 0).You may asome that when there is a request to include a new client in the list(code 1)は、there isのother request in the list of the list of the the the same and the the inder.inder.inder.oris.ore the.and a pristy P is less than 107.The client may arrive for being served multiple times,and each time may obint a different prority.
Output
For each request with code 2 or 3、the program has to prinent、in a separate line of the standard output、the identifer of the served client.If the request arrives when the waiting list is emipty、then the Prot Pringzers.
Sample Input

2
1 20 14
1 30 3
2
1 10 99
3
2
2
0

Sample Output

0
20
30
10
0

ノードを挿入します.pは優先順位で、kは顧客番号です.
優先度が一番大きいノードを削除します.
優先度が一番小さいノードを削除します.
作り方はいろいろあります.splayを勉強したので、水を飲みました.
以前はsplayがとても高いと思っていましたが、この二日間見てみました.以前のデータ構造で習った二叉のバランスツリーとb+,b-木の難易度はそんなに違いません.
水中コード

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 1000001
int ch[maxn][2],val[maxn],fa[maxn],id[maxn],root;
int cnt = 0;
int newnode(int k,int p){
    val[cnt]=p;
    id[cnt]=k;
    ch[cnt][0]=ch[cnt][1]=0;
    return cnt++;
}
void init(){
    root = 0;
    cnt = 1;
    ch[0][0] = ch[0][1] = fa[0] = 0;
}
void rotate(int n){
    int f = fa[n],ff=fa[f];
    int x = (ch[f][1] == n),x1=(ch[ff][1]==f);
    ch[ff][x1] = n;
    ch[f][x] = ch[n][!x];
    ch[n][!x] = f;
    fa[ch[f][x]] = f;
    fa[n] = ff;
    fa[f] = n;
}
void splay(int n,int p){
    while(fa[n] != p){
        int f = fa[n],ff=fa[f];
        if(ff==p)rotate(n);
        else if((ch[ff][1] == f)==(ch[f][1]==n))rotate(f),rotate(n);
        else rotate(n),rotate(n);
    }
}
int findmax(int n){
    while(ch[n][1] != 0) n=ch[n][1];
    return n;
}
int findmin(int n){
    while(ch[n][0] != 0) n=ch[n][0];
    return n;
}
int jion(int p,int q,int f){
    if(p == 0) return q;
    int m = findmax(p);
    splay(m,f);
    ch[m][1] = q;
    fa[q]=m;
    return m;
}
void add(int k,int p){
    int q = newnode(k,p);
    if(ch[root][1] == 0) ch[root][1] = q,fa[q]=root;
    else {
        int x = ch[root][1],y=x;
        while(x){
            y = x;
            if(val[x]>p) x=ch[x][0];
            else x=ch[x][1];
        }
        if(val[y] > p) ch[y][0]=q,fa[q]=y;
        else ch[y][1] = q,fa[q]=y;
        ///splay(q,root);
    }
}
void drop(int n){
    if(n==0){
        printf("0
");
        return ;
    }
    printf("%d
",id[n]);
    splay(n,root);
    int p = jion(ch[n][0],ch[n][1],n);
    ch[root][1] = p;
    fa[p] = root;
}

int main(){
    int n,p,k;
    init();
    while(scanf("%d",&n),n){
        if(n == 2)    drop(findmax(ch[root][1]));
        else if(n ==3)drop(findmin(ch[root][1]));
        else {
            scanf("%d%d",&k,&p);
            add(k,p);
        }
    }
    return 0;
}