Splay树模板题入门

本文主要是介绍Splay树模板题入门，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

模板题①：HDU 4453 Looploop

以下代码摘自：https://blog.csdn.net/ck_boss/article/details/48031457

意识到这样的题原来才是模板题之后，我才知道Splay树中，翻转区间是很基本的功能。学到技巧：对区间[L,R]的翻转是用结点L-1和R+1作为一个边界，然后对其子节点标记翻转。很多Splay树的操作都利用了这个边界设置的技巧。
这里有区间增，区间翻转，单点增删，删除子树，求Kth小，splay的旋转结点，这些功能。

总的来说，核心还是Splay函数的旋转功能，即把一个结点变为另一个结点的子节点，或者之间变为根，围绕这一点展开了各种功能。

理解一点，树里面的大小关系就是左右关系，和实际包含的结点权值无关。

#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 220000;#define Key_value tree[tree[root][1]][0]int p[maxn], n, m, k1, k2;int tree[maxn][2], rev[maxn], add[maxn], sz[maxn], pre[maxn], key[maxn];
int root, tot1, tot2, s[maxn];void newnode(int& x, int fa, int v) {if (tot2)x = s[tot2--];else x = ++tot1;tree[x][0] = tree[x][1] = rev[x] = add[x] = 0;sz[x] = 1; pre[x] = fa; key[x] = v;
}
void del_tree(int x) {if (x) {s[++tot2] = x;del_tree(tree[x][0]);del_tree(tree[x][1]);}
}
void update_rev(int x) {if (!x)return;swap(tree[x][0], tree[x][1]);rev[x] ^= 1;
}
void update_add(int x, int d) {if (!x)return;key[x] += d; add[x] += d;
}
void pushup(int x) {sz[x] = sz[tree[x][0]] + sz[tree[x][1]] + 1;
}
void pushdown(int x) {if (rev[x]) {update_rev(tree[x][0]);update_rev(tree[x][1]);rev[x] = 0;}if (add[x]) {update_add(tree[x][0], add[x]);update_add(tree[x][1], add[x]);add[x] = 0;}
}
void Rotate(int x, int c) {int y = pre[x];pushdown(y);pushdown(x);tree[y][!c] = tree[x][c];pre[tree[x][c]] = y;if (pre[y])tree[pre[y]][tree[pre[y]][1] == y] = x;pre[x] = pre[y];tree[x][c] = y;pre[y] = x;pushup(y);
}
void splay(int x, int goal) {pushdown(x);while (pre[x] != goal) {if (pre[pre[x]] == goal) {//再转一次就完成了pushdown(pre[x]); pushdown(x);Rotate(x, tree[pre[x]][0] == x);}else {pushdown(pre[pre[x]]); pushdown(pre[x]); pushdown(x);int y = pre[x];int c = (tree[pre[y]][0] == y);if (tree[y][c] == x) {//三点不共线Rotate(x, !c);Rotate(x, c);}else {//三点共线Rotate(y, c);Rotate(x, c);}}}pushup(x);if (goal == 0)root = x;
}
int kth(int x, int k) {pushdown(x);int t = sz[tree[x][0]] + 1;if (k == t)return x;if (t < k)return kth(tree[x][1], k - t);else return kth(tree[x][0], k);
}
void ADD(int L, int R, int d) {splay(kth(root, L), 0);splay(kth(root, R + 2), root);update_add(Key_value, d);pushup(tree[root][1]);pushup(root);
}
void REVERSE(int L, int R) {splay(kth(root, L), 0);splay(kth(root, R + 2), root);update_rev(Key_value);pushup(tree[root][1]);pushup(root);
}
void DELETE(int k) {//删除k位置的结点splay(kth(root, k), 0);splay(kth(root, k + 2), root);del_tree(Key_value);pre[Key_value] = 0;Key_value = 0;pushup(tree[root][1]);pushup(root);
}
void INSERT(int k, int v) {//增加结点到k位置的右边splay(kth(root, k + 1), 0);splay(kth(root, k + 2), root);newnode(Key_value, tree[root][1], v);pushup(tree[root][1]);pushup(root);
}
void buildtree(int& x, int L, int R, int fa) {if (L > R)return;int mid = (L + R) >> 1;newnode(x, fa, p[mid]);buildtree(tree[x][0], L, mid - 1, x);buildtree(tree[x][1], mid + 1, R, x);pushup(x);
}
void init(int n) {root = tot1 = tot2 = 0;tree[root][0] = tree[root][1] = pre[root] = sz[root] = 0;newnode(root, 0, inf);//设置左右两个边界点,实际操作是在这两个点之间newnode(tree[root][1], root, inf);buildtree(Key_value, 1, n, tree[root][1]);pushup(tree[root][1]);pushdown(root);
}
int main(void) {string cmd; int kase = 0;while (~scanf("%d %d %d %d", &n, &m, &k1, &k2) && (n || m || k1 || k2)) {for (int i = 1; i <= n; i++)scanf("%d", &p[i]);init(n);printf("Case #%d:\n", ++kase);while (m--) {cin >> cmd;if (cmd == "query") {splay(kth(root, 1), 0);splay(kth(root, 3), root);printf("%d\n", key[Key_value]);}else if (cmd == "move") {int to;scanf("%d", &to);if (to == 1) {//位置左移,最右侧结点放到最左侧splay(kth(root, n), 0);splay(kth(root, n + 2), root);int tmp = key[Key_value];DELETE(n);//取出最右边结点INSERT(0, tmp);//放到最左侧}else {//与上面相反splay(kth(root, 1), 0);splay(kth(root, 3), root);int tmp = key[Key_value];DELETE(1);INSERT(n - 1, tmp);}}else if (cmd == "delete") {DELETE(1); n--;//删除当前指向的结点}else if (cmd == "insert") {int v; scanf("%d", &v);INSERT(1, v); n++;//增加结点到当前指向位置的右侧}else if (cmd == "reverse") {REVERSE(1, k1);}else if (cmd == "add") {int d; scanf("%d", &d);ADD(1, k2, d);}}}return 0;
}

…看到了Kuang_bin大神的模板，看来Key_value的命名是比较流行的了。

模板题②：HDU 1890 Robotic Sort
这里有删除根节点的写法，可供参考。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
int root;
int rev[maxn], pre[maxn], sz[maxn];
int tree[maxn][2];
struct node {int val, id;bool operator < (const node& A)const {if (val == A.val)return id < A.id;return val < A.val;}
}nodes[maxn];
void pushup(int x) {sz[x] = sz[tree[x][0]] + sz[tree[x][1]] + 1;
}
void update_rev(int x) {if (!x)return;swap(tree[x][0], tree[x][1]);rev[x] ^= 1;
}
void pushdown(int x) {if (rev[x]) {update_rev(tree[x][0]);update_rev(tree[x][1]);rev[x] = 0;}
}
void Rotate(int x, int c) {//c=1右旋,c=0左旋int y = pre[x];pushdown(y);pushdown(x);tree[y][!c] = tree[x][c];//把x的儿子送给y当儿子pre[tree[x][c]] = y;//让y的新儿子认y当父亲if (pre[y])tree[pre[y]][tree[pre[y]][1] == y] = x;//y的父亲收x当儿子,不要y了pre[x] = pre[y];//x认新父亲tree[x][c] = y;//y成了x的儿子pre[y] = x;//y认x当父亲pushup(y);pushup(x);
}
void splay(int x, int goal) {//把节点x旋转为goal的儿子,如果goal=0,则旋转到根pushdown(x);while (pre[x] != goal) {if (pre[pre[x]] == goal) {pushdown(pre[x]); pushdown(x);Rotate(x, tree[pre[x]][0] == x);}else {pushdown(pre[pre[x]]); pushdown(pre[x]); pushdown(x);int y = pre[x];int c = (tree[pre[y]][0] == y);if (tree[y][c] == x) {//c=1,y有右儿子是x,y是父亲的左儿子Rotate(x, !c);    //c=0,y的左儿子是x,y是父亲的右儿子Rotate(x, c);}else {Rotate(y, c);Rotate(x, c);}}}pushup(x);if (goal == 0)root = x;
}
int get_max(int x) {pushdown(x);while (tree[x][1]) {x = tree[x][1];pushdown(x);}return x;
}
void del_root() {//删除根节点if (tree[root][0] == 0) {root = tree[root][1];pre[root] = 0;}else {int m = get_max(tree[root][0]);splay(m, root);tree[m][1] = tree[root][1];pre[tree[root][1]] = m;root = m;pre[root] = 0;pushup(root);}
}
void newnode(int& x, int fa, int val) {x = val;pre[x] = fa;sz[x] = 1;rev[x] = 0;tree[x][0] = tree[x][1] = 0;
}
void buildtree(int& x, int l, int r, int fa) {if (l > r)return;int mid = (l + r) >> 1;newnode(x, fa, mid);buildtree(tree[x][0], l, mid - 1, x);buildtree(tree[x][1], mid + 1, r, x);pushup(x);
}
void init(int n) {root = 0;tree[root][0] = tree[root][1] = pre[root] = sz[root] = 0;buildtree(root, 1, n, 0);
}
int main(void) {int n;while (~scanf("%d", &n) && n) {init(n);for (int i = 1; i <= n; i++) {scanf("%d", &nodes[i].val);nodes[i].id = i;}sort(nodes + 1, nodes + n + 1);for (int i = 1; i < n; i++) {splay(nodes[i].id, 0);update_rev(tree[root][0]);printf("%d ", i + sz[tree[root][0]]);del_root();}printf("%d\n", n);}return 0;
}

模板题③：HDU 3726 Graph and Queries
这题很经典，这里有Treap树的题解：https://blog.csdn.net/TK_wang_/article/details/108615120

#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 2e6+5;
#define Key_value tree[tree[root][1]][0]
int val[maxn], n, m, kase;
int tree[maxn][2],sz[maxn], pre[maxn], key[maxn];
int root, tag[maxn];
int fa[maxn];
struct edge{int u, v;
}e[maxn];
struct command{int x, k, cas;
}cmd[maxn];
void newnode(int& x, int fa, int pos, int v) {x = pos;tree[x][0] = tree[x][1] = 0;sz[x] = 1; pre[x] = fa; key[x] = v;
}
void pushup(int x) {sz[x] = sz[tree[x][0]] + sz[tree[x][1]] + 1;
}
void Rotate(int x, int c) {int y = pre[x];tree[y][!c] = tree[x][c];pre[tree[x][c]] = y;if (pre[y])tree[pre[y]][tree[pre[y]][1] == y] = x;pre[x] = pre[y];tree[x][c] = y;pre[y] = x;pushup(y);
}
void splay(int x, int goal) {while (pre[x] != goal) {if (pre[pre[x]] == goal) {//再转一次就完成了Rotate(x, tree[pre[x]][0] == x);}else {int y = pre[x];int c = (tree[pre[y]][0] == y);if (tree[y][c] == x) {//三点不共线Rotate(x, !c);Rotate(x, c);}else {//三点共线Rotate(y, c);Rotate(x, c);}}}pushup(x);if (goal == 0)root = x;
}
int kth(int x, int k) {int t = sz[tree[x][1]] + 1;if (k == t)return x;if (t < k)return kth(tree[x][0], k - t);else return kth(tree[x][1], k);
}
void INSERT(int pos, int v) {int x = root;if (!x) {newnode(x, 0, pos, v);return;}while (tree[x][key[x] < v]) {x = tree[x][key[x] < v];}newnode(tree[x][key[x] < v], x, pos, v);splay(tree[x][key[x] < v], 0);
}
int get_min(int rt) {while (tree[rt][0])rt = tree[rt][0];return rt;
}
void del_root() {if (tree[root][0] == 0 || tree[root][1] == 0) {root = tree[root][0] + tree[root][1];pre[root] = 0;return;}int k = get_min(tree[root][1]);splay(k, root);//把仅比root大的转为根,删除rootKey_value = tree[root][0];//显然k的左子树为空root = tree[root][1];pre[tree[root][0]] = root;//更新父亲pre[root] = 0;pushup(root);
}
int findfa(int x) {return x == fa[x] ? x : fa[x] = findfa(fa[x]);
}
void bing(int r) {if (!r)return;bing(tree[r][0]);bing(tree[r][1]);INSERT(r, val[r]);
}
void merge(int x, int y) {int fa1 = findfa(x), fa2 = findfa(y);if (fa1 == fa2)return;fa[fa1] = fa2;splay(fa1, 0);splay(fa2, 0);if (sz[fa1] > sz[fa2])swap(fa1, fa2);root = fa2;bing(fa1);splay(fa2, 0);
}
int main(void) {while (~scanf("%d %d", &n, &m) && (n || m)) {for (int i = 1; i <= n; i++) {scanf("%d", &val[i]);fa[i] = i;}for (int i = 1; i <= m; i++) {scanf("%d %d", &e[i].u, &e[i].v);tag[i] = 0;}int q_num = 0;while (1) {char str[5];scanf("%s", str);if (str[0] == 'E')break;q_num++;if (str[0] == 'D') {scanf("%d", &cmd[q_num].x);cmd[q_num].cas = 1;tag[cmd[q_num].x] = 1;}else if (str[0] == 'Q') {scanf("%d %d", &cmd[q_num].x,&cmd[q_num].k);cmd[q_num].cas = 2;}else {int x, v;scanf("%d %d", &x, &v);cmd[q_num].cas = 3;cmd[q_num].x = x;cmd[q_num].k = val[x];val[x] = v;}}for (int i = 1; i <= n; i++)newnode(root, 0, i, val[i]);for (int i = 1; i <= m; i++) {if (tag[i])continue;merge(e[i].u, e[i].v);}double ans = 0;int cnt = 0;for (int i = q_num; i; i--) {if (cmd[i].cas == 1) {int x = cmd[i].x;merge(e[x].u, e[x].v);              }else if (cmd[i].cas == 2) {int x = cmd[i].x, k = cmd[i].k;cnt++;splay(x, 0);if (sz[root] < k || k <= 0)continue;ans += key[kth(root, k)];}else {int x = cmd[i].x, v = cmd[i].k;splay(x, 0);val[root] = v;del_root();INSERT(x, v);}}if (cnt == 0)cnt++;printf("Case %d: %.6f\n", ++kase, ans / cnt);}return 0;
}