POJ 3481 Splay

传送门：POJ 3481

题解

用二分查找建树， 然后把新节点放到root下， 这样能够保证查询复杂度平摊为O(logn); 查询后， 把查找的节点删掉(修改父亲和某个孩子指针， 数组模拟)， 因为新建的时候旋转， 所以这里的节点不会又两个孩子 还有一种map解法

---

Splay code:

#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define debug 0 #define M(a, b) memset(a, b, sizeof(a)) #define ls ch[x][0] #define rs ch[x][1] const int maxn = (1e6 + 10); struct Splay{ int pre[maxn], ch[maxn][2], k[maxn], v[maxn]; int root, rt; Splay() { root = rt = 0; M(pre, 0); M(ch, 0); M(k, 0); M(v, 0); } void newNode(int &x, int _k, int c, int f) {//creat x = ++rt; v[x] = c; k[x] = _k; pre[x] = f; } void Rotate(int x, int d) { int y = pre[x]; ch[y][!d] = ch[x][d]; pre[ch[y][!d]] = y; pre[x] = pre[y]; ch[x][d] = y; if (pre[y]) ch[pre[y]][ch[pre[y]][1] == y] = x; pre[y] = x; } void splay(int x, int to) { while (pre[x] != to) { if (pre[pre[x]] == to) Rotate(x, ch[pre[x]][0] == x); else { int y = pre[x], z = pre[y]; int f = (ch[z][1] == y); if (ch[y][f] == x) Rotate(y, !f), Rotate(x, !f); else Rotate(x, f), Rotate(x, !f); } } if (!to) root = x; } void insert_node(int _k, int v) {//二分查找新建结点 int x = root; int r = root; while (x) { r = x; if (k[x] < _k) x = rs; else x = ls; } newNode(ch[r][k[r] < _k] , _k, v, r); splay(ch[r][k[r] < _k], root);//旋转 ch[0][0] = ch[0][1] = 0; } int query(int d) {//查询 d -= 2; int x = root; while (ch[x][!d]) x = ch[x][!d]; if (x == root) root = ch[x][d];//若是根， 修改根 ch[pre[x]][!d] = ch[x][d];//修改父亲和孩子 pre[ch[x][d]] = pre[x]; return v[x]; } }sp; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif //debug int op, k, v; while (cin >> op, op) { if (op == 1) { cin >> k >> v; sp.insert_node(v, k); } else { cout << sp.query(op) << endl; } } return 0; }

map code:

#include<iostream> #include<cstring> #include<cstdio> #include<map> using namespace std; #define debug 0 #define M(a, b) memset(a, b, sizeof(a)) #define ls ch[x][0] #define rs ch[x][1] const int maxn = (1e6 + 10); int main() { #if debug freopen("in.txt", "r", stdin); #endif //debug cin.tie(0); cin.sync_with_stdio(false); int op, k, v; map<int, int>mp; while (cin >> op, op) { map<int, int>::iterator it; if (op == 1) { cin >> k >> v; mp[v] = k; } else { if (mp.empty()) { cout << "0" << endl; } else { if (op == 2) { it = --mp.end(); cout << it->second << endl; mp.erase(it->first); } else { it = mp.begin(); cout << it->second << endl; mp.erase(it->first); } } } } return 0; }