【POJ】3481 Double Queue

 1 #include<cstdio>
 2 #define MAXN 100010
 3 struct SplayTree {
 4     int size, root;
 5     int next[MAXN][2], pre[MAXN], key[MAXN], pos[MAXN];
 6     void Init() {
 7         size = root = 0;
 8         next[0][0] = next[0][1] = 0;
 9     }
10     void NewNode(int &rt, int father, int val, int id) {
11         rt = ++size;
12         next[rt][0] = next[rt][1] = 0;
13         pre[rt] = father;
14         key[rt] = val;
15         pos[rt] = id;
16     }
17     void Rotate(int x, int kind) {
18         int y = pre[x];
19         next[y][!kind] = next[x][kind];
20         pre[next[x][kind]] = y;
21         pre[x] = pre[y];
22         if (pre[y])
23             next[pre[y]][next[pre[y]][1] == y] = x;
24         next[x][kind] = y;
25         pre[y] = x;
26     }
27     void Splay(int x, int goal) {
28         while (pre[x] != goal) {
29             if (next[pre[x]][0] == x)
30                 Rotate(x, 1);
31             else
32                 Rotate(x, 0);
33         }
34         if (!goal)
35             root = x;
36     }
37     void Insert(int val, int id) {
38         int x;
39         for (x = root; next[x][key[x] < val]; x = next[x][key[x] < val])
40             ;
41         NewNode(next[x][key[x] < val], x, val, id);
42         Splay(next[x][key[x] < val], 0);
43     }
44     void Delete(int x) {
45         if (x == root) {
46             if (!next[x][0] && !next[x][1])
47                 Init();
48             else {
49                 int t = next[x][0] ? 0 : 1;
50                 pre[next[x][t]] = 0;
51                 root = next[x][t];
52             }
53         } else {
54             int y, t;
55             y = pre[x];
56             t = (next[y][1] == x);
57             next[y][t] = next[x][!t];
58             pre[next[x][!t]] = y;
59             Splay(y, 0);
60         }
61     }
62     void Lowest() {
63         int x = root;
64         if (x) {
65             for (; next[x][0]; x = next[x][0])
66                 ;
67             printf("%d\n", pos[x]);
68             Delete(x);
69         } else
70             puts("0");
71     }
72     void Highest() {
73         int x = root;
74         if (x) {
75             for (; next[x][1]; x = next[x][1])
76                 ;
77             printf("%d\n", pos[x]);
78             Delete(x);
79         } else
80             puts("0");
81     }
82 } tree;
83 int main() {
84     int cmd, val, id;
85     tree.Init();
86     while (scanf("%d", &cmd), cmd) {
87         if (cmd == 1) {
88             scanf("%d%d", &id, &val);
89             tree.Insert(val, id);
90         } else if (cmd == 2)
91             tree.Highest();
92         else
93             tree.Lowest();
94     }
95     return 0;
96 }