Splay树 模板题入门

2024-04-13 03:08
文章标签 模板 入门 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;
}

总结：Splay树的灵活度比较高，代码量大，要善于思考才能构造出符合题目要求的各种操作，它能做到一些线段树做不了的事情，是一种很有价值的数据结构。

这篇关于Splay树 模板题入门的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/898978。

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
poj3468(线段树成段更新模板题)

poj3468(线段树成段更新模板题)

题意：包括两个操作：1、将[a.b]上的数字加上v；2、查询区间[a,b]上的和 下面的介绍是下解题思路： 首先介绍  lazy－tag思想：用一个变量记录每一个线段树节点的变化值，当这部分线段的一致性被破坏我们就将这个变化值传递给子区间，大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作，那么就从根节点[1,n]开始调用update函数进行操作，如果刚好执行到一个子节点，
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
poj 1258 Agri-Net（最小生成树模板代码）

poj 1258 Agri-Net（最小生成树模板代码）

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码：效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n
阅读更多...
数论入门整理（updating）

数论入门整理（updating）

一、gcd lcm 基础中的基础，一般用来处理计算第一步什么的，分数化简之类。 LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } <pre name="code" class="cpp">LL lcm(LL a, LL b){LL c = gcd(a, b);return a / c * b;} 例题：
阅读更多...
uva 1342 欧拉定理（计算几何模板）

uva 1342 欧拉定理（计算几何模板）

题意： 给几个点，把这几个点用直线连起来，求这些直线把平面分成了几个。 解析： 欧拉定理： 顶点数 + 面数 - 边数= 2。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc
阅读更多...
uva 11178 计算集合模板题

uva 11178 计算集合模板题

题意： 求三角形行三个角三等分点射线交出的内三角形坐标。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <
阅读更多...
Java 创建图形用户界面（GUI）入门指南（Swing库 JFrame 类）概述

Java 创建图形用户界面（GUI）入门指南（Swing库 JFrame 类）概述

概述 基本概念 Java Swing 的架构 Java Swing 是一个为 Java 设计的 GUI 工具包，是 JAVA 基础类的一部分，基于 Java AWT 构建，提供了一系列轻量级、可定制的图形用户界面（GUI）组件。 与 AWT 相比，Swing 提供了许多比 AWT 更好的屏幕显示元素，更加灵活和可定制，具有更好的跨平台性能。 组件和容器 Java Swing 提供了许多
阅读更多...
【IPV6从入门到起飞】5-1 IPV6+Home Assistant(搭建基本环境)

【IPV6从入门到起飞】5-1 IPV6+Home Assistant(搭建基本环境)

【IPV6从入门到起飞】5-1 IPV6+Home Assistant #搭建基本环境 1 背景2 docker下载 hass3 创建容器4 浏览器访问 hass5 手机APP远程访问hass6 更多玩法 1 背景 既然电脑可以IPV6入站，手机流量可以访问IPV6网络的服务，为什么不在电脑搭建Home Assistant（hass），来控制你的设备呢？@智能家居 @万物互联
阅读更多...
poj 2104 and hdu 2665 划分树模板入门题

poj 2104 and hdu 2665 划分树模板入门题

题意： 给一个数组n（1e5）个数，给一个范围（fr， to， k），求这个范围中第k大的数。 解析： 划分树入门。 bing神的模板。 坑爹的地方是把-l 看成了-1........ 一直re。 代码： poj 2104： #include <iostream>#include <cstdio>#include <cstdlib>#include <al
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2