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。

相关文章

从入门到精通MySQL联合查询

从入门到精通MySQL联合查询

《从入门到精通MySQL联合查询》：本文主要介绍从入门到精通MySQL联合查询,本文通过实例代码给大家介绍的非常详细,需要的朋友可以参考下... 目录摘要1. 多表联合查询时mysql内部原理2. 内连接3. 外连接4. 自连接5. 子查询6. 合并查询7. 插入查询结果摘要前面我们学习了数据库设计时要满
阅读更多...
从入门到精通C++11 ＜chrono＞ 库特性

从入门到精通C++11 ＜chrono＞ 库特性

《从入门到精通C++11＜chrono＞库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段（Durat
阅读更多...
解析C++11 static_assert及与Boost库的关联从入门到精通

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识：传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决
阅读更多...
从入门到精通MySQL 数据库索引(实战案例)

从入门到精通MySQL 数据库索引(实战案例)

《从入门到精通MySQL数据库索引(实战案例)》索引是数据库的目录,提升查询速度,主要类型包括BTree、Hash、全文、空间索引,需根据场景选择,建议用于高频查询、关联字段、排序等,避免重复率高或... 目录一、索引是什么？能干嘛？核心作用：二、索引的 4 种主要类型（附通俗例子）1. BTree 索引（
阅读更多...
Redis 配置文件使用建议redis.conf 从入门到实战

Redis 配置文件使用建议redis.conf 从入门到实战

《Redis配置文件使用建议redis.conf从入门到实战》Redis配置方式包括配置文件、命令行参数、运行时CONFIG命令,支持动态修改参数及持久化,常用项涉及端口、绑定、内存策略等,版本8... 目录一、Redis.conf 是什么？二、命令行方式传参（适用于测试）三、运行时动态修改配置（不重启服务
阅读更多...
MySQL DQL从入门到精通

MySQL DQL从入门到精通

《MySQLDQL从入门到精通》通过DQL,我们可以从数据库中检索出所需的数据,进行各种复杂的数据分析和处理,本文将深入探讨MySQLDQL的各个方面,帮助你全面掌握这一重要技能,感兴趣的朋友跟随小... 目录一、DQL 基础：SELECT 语句入门二、数据过滤：WHERE 子句的使用三、结果排序：ORDE
阅读更多...
Python中OpenCV与Matplotlib的图像操作入门指南

Python中OpenCV与Matplotlib的图像操作入门指南

《Python中OpenCV与Matplotlib的图像操作入门指南》：本文主要介绍Python中OpenCV与Matplotlib的图像操作指南,本文通过实例代码给大家介绍的非常详细,对大家的学... 目录一、环境准备二、图像的基本操作1. 图像读取、显示与保存 使用OpenCV操作2. 像素级操作3.
阅读更多...
Java如何根据word模板导出数据

Java如何根据word模板导出数据

《Java如何根据word模板导出数据》这篇文章主要为大家详细介绍了Java如何实现根据word模板导出数据,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... pom.XML文件导入依赖 <dependency> <groupId>cn.afterturn</groupId>
阅读更多...
POI从入门到实战轻松完成EasyExcel使用及Excel导入导出功能

POI从入门到实战轻松完成EasyExcel使用及Excel导入导出功能

《POI从入门到实战轻松完成EasyExcel使用及Excel导入导出功能》ApachePOI是一个流行的Java库,用于处理MicrosoftOffice格式文件,提供丰富API来创建、读取和修改O... 目录前言:Apache POIEasyPoiEasyExcel一、EasyExcel1.1、核心特性
阅读更多...
Python中Flask模板的使用与高级技巧详解

Python中Flask模板的使用与高级技巧详解

《Python中Flask模板的使用与高级技巧详解》在Web开发中,直接将HTML代码写在Python文件中会导致诸多问题,Flask内置了Jinja2模板引擎,完美解决了这些问题,下面我们就来看看F... 目录一、模板渲染基础1.1 为什么需要模板引擎1.2 第一个模板渲染示例1.3 模板渲染原理二、模板
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2