当前位置: 代码迷 >> 综合 >> 【splay】hdu 3487
  详细解决方案

【splay】hdu 3487

热度:50   发布时间:2023-12-11 15:08:06.0

第一次接触splay。找了几道题写自己的模板。。每次写错东西都到处找错,splay的操作方式真的很多,虽然说思路简单。。但是真的很怕写错orz

传说中能解决各种区间翻转问题的乱搞树。就是splay,他的核心,就是splay。应该叫rotate,翻转吧。

学习旋转的时候参考了这篇博客:
http://www.cnblogs.com/yousiki/p/6147455.html
背景有点花。。f12把background去了。

如果要看图的话,可以看那边,这里就不画图了。
旋转,通常有左旋和右旋。

对于左旋来说,假设p为根节点,x为p的左儿子节点,现在要将x旋转到p那个位置。
那么,p会成为x的右儿子结点,那这个时候,x的右儿子结点的东西应该放到哪里去呢。
可以想象下,p原本的左儿子节点是x,但是现在p成了x的右儿子结点,他的左儿子节点就空了。
那么我们可以把x的右儿子结点接到p的左儿子节点上。那么这样就完成了一次左旋。

至于为什么这样操作之后,这个树还是满足二叉平衡树呢,因为二叉平衡树满足,左儿子树的数一定比当前节点小,右儿子树的数一定比当前节点大。
那把p变成x的右儿子,原本p及p的右儿子就一定比x大,那旋转之后照样满足。
把x的右儿子节点变成p的左儿子节点,由于x的右儿子结点一定比x大,且比p小,操作之后,依然满足。
所以旋转是成立的。

dalao们说,通常单旋是不够的,要双旋,单旋容易给退化成链。

那么当p为根时,我们进行一次左旋或者右旋就可以了,称为zig-step
如果当p不为根时,有两种情况。
一种是p和x同为左儿子,或者同为右儿子,那么我们只需要对p先做一次zig-step,再对x做一次zig-step即可。这种称之为zig-zig-step
如果p和x不为同方向的儿子,我们需要先对x进行一次zig-step到p,再进行反着得zig-step,也就叫zag-step到根。这种称之为zig-zag-step

图的话就不画啦,字太丑orz。可以理论上去偷看下别人的旋转。

旋转操作完毕之后,就可以做各式各样的操作了。
例如,求区间和,求区间数,翻转区间,截断区间。


说了那么多,还是做一下经典题目。

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3487

题目大意:
有一个长度为n的序列:1…n
有两种操作
1、CUT,将 [a, b]下标的数切断,切断后找到第c个位置的数,放在他后面。
2、FLIP,将[a, b]区间翻转


思路:
对于截断,可以这么操作。
将a-1位置的数旋转到root
将b+1位置的数旋转到root的右儿子结点
那么,现在root的右儿子的左儿子节点的那棵子树就是我们要操作的区间。
先将root右儿子和区间树的关系去除。
再找出第c的位置。
将c旋转到root。
这个时候将区间树作为root的右儿子的左儿子,操作完成。

对于翻转,可以这么操作。
同理截断
将a-1位置的数旋转到root
将b+1位置的数旋转到root的右儿子结点。
那么现在root的右儿子的左儿子节点的那棵子树就是我们要操作的区间。
我们给他们的root打上lazy标记,证明这个区间要翻转。
当进行rotate的时候,我们更新标记,像线段树那样,将要翻转的点的两个子树交换即可。

代码上都打满了注释。

/* @resources: @date: 2017-09-02 @author: QuanQqqqq @algorithm: splay */
#include <stdio.h>
#include <algorithm>
#include <string.h>#define ll long longusing namespace std;int n;struct SplayTree {const static int MAX_SIZE = 3e5 + 10;const static int INF = 0x7ffffff;int tree[MAX_SIZE][2], father[MAX_SIZE]; //该点的左右儿子,该点的爸爸节点, int size[MAX_SIZE];                      //该点的子节点数 int val[MAX_SIZE];                       //每个点的价值 int root, sz;                            //该树的根,该树的节点数int cnt;                                 //中序遍历指针 int rev[MAX_SIZE];                       //翻转区间,懒惰更新int node[MAX_SIZE];                      //记录节点的下标void new_node(int &r, int fa, int v) {r = ++sz;father[r] = fa;val[r] = v;rev[r] = tree[r][0] = tree[r][1] = 0;}void modify(int x) {if (!x) {return ;}rev[x] ^= 1;}//更新节点数 void push_up(int r) {size[r] = size[tree[r][0]] + size[tree[r][1]] + 1;}//lazy更新 void push_down(int r) {if (r && rev[r]) {swap(tree[r][0], tree[r][1]); //翻转 modify(tree[r][0]);modify(tree[r][1]);modify(r);}}void build(int &rt, int l, int r, int fa) {   //建一棵满的二叉平衡树 if (l > r) {return ;}int mid = l + r >> 1;new_node(rt, fa, mid);build(tree[rt][0], l, mid - 1, rt);build(tree[rt][1], mid + 1, r, rt);push_up(rt);}void clear() {sz = root = cnt = 0;size[root] = tree[0][0] = tree[0][1] = rev[0] = father[0] = 0;memset(rev, 0, sizeof(rev)); new_node(root, 0, -1);new_node(tree[root][1], root, -1);size[root] = 2;build(tree[tree[root][1]][0], 1, n, tree[root][1]);  //建一棵在n+1左边的完全二叉平衡树 push_up(tree[root][1]);push_up(root);}void rotate(int x, int k) {   //x是节点,k判断是左旋还是右旋 int y = father[x];push_down(y);push_down(x);tree[y][!k] = tree[x][k]; //先变两边的儿子 father[tree[x][k]] = y;     //再将x的儿子的爸爸变成y if (father[y]) {          //如果不是root,将y爸爸的儿子也变一下 tree[father[y]][tree[father[y]][1] == y] = x;}father[x] = father[y];    //更新x的父亲成y的父亲 father[y] = x;            //更新y的父亲成x tree[x][k] = y;           //更新x的儿子成y push_up(y);}void splay(int x, int r) {    //将x旋转到r的儿子,这里注意是儿子! if (r == 0) {root = x;}push_down(x);while (father[x] != r) {if (father[father[x]] == r) { //zig-step rotate(x, tree[father[x]][0] == x);return ;}int y = father[x];int k = tree[father[y]][0] == y;  //判断上上层是否是左边 if (tree[y][k] == x) { // zig-zag-steprotate(x, !k);rotate(x, k);} else {                      // zig-zig-steprotate(y, k);rotate(x, k);}} push_up(x);} int insert(int v) { //插入值,插入完毕后进行splay操作,将插入的位置splay到root int r = root;while (tree[r][val[r] < v]) {if (val[r] == v) {splay(r, 0);return 0;}push_down(r);r = tree[r][val[r] < v];}new_node(tree[r][val[r] < v], r, v);splay(tree[r][val[r] < v], 0);return 1;}int get_kth(int r, int k) { //获得第k大的root push_down(r);int siz = size[tree[r][0]];if (siz == k - 1) {return r;}if (siz >= k) {return get_kth(tree[r][0], k);} else {return get_kth(tree[r][1], k - siz - 1);}}int get_min(int x) {  //获得最小值的位置 push_down(x);while (tree[x][0]) {x = tree[x][0];push_down(x);}return x;}int get_max(int x) {  //获得最大值的位置 push_down(x);while (tree[x][1]) {x = tree[x][1];push_down(x);}return x;}int get_next(int x) {  //获得比x下标大一点的值 push_down(x);int rg = tree[x][1];push_down(rg);if (rg == 0) {return INF;}while (tree[rg][0]) {rg = tree[rg][0];push_down(rg);}return val[rg] - val[x]; //这里返回时可以更改 } int get_pre(int x) {   //获得比x下标小一点的值 push_down(x);int lt = tree[x][0];push_down(lt);if (lt == 0) {return INF;}while (tree[lt][1]) {lt = tree[lt][1];push_down(lt);}return val[x] - val[lt];}void cut(int a, int b, int c) {     //将[a,b]切断,放在切断后第c个数后面int x = get_kth(root, a);       //这里由于树是[0,n+1]的,所以要找的区间如果是[a,b]则需要将 a-1旋转到根,b+1旋转到a-1的子根,那么b+1的左子树就是要的区间 int y = get_kth(root, b + 2);   //又由于从0开始,所以都+1splay(x, 0);splay(y, root);int p = tree[tree[root][1]][0]; //区间树的根 tree[tree[root][1]][0] = 0;     //切断 push_up(tree[root][1]);push_up(root);                  //更新一下节点数int z = get_kth(root, c + 1);   //切断后就可以找第c位数splay(z, 0);                    //旋转到根int m = get_min(tree[root][1]); //找一下右子树最小的位置splay(m, root);                 //旋转到根的右儿子,那么这个最小的位置的左儿子就是空的了tree[tree[root][1]][0] = p;     //放回去 father[tree[tree[root][1]][0]] = tree[root][1];push_up(tree[root][1]);         //更新节点 push_up(root);} void reversal(int a, int b) { //[a, b]内区间交换 int x = get_kth(root, a);int y = get_kth(root, b + 2);splay(x, 0);    //左区间旋转到根 splay(y, root); //右区间旋转到根的左边,那么根的右儿子结点的左儿子节点为所需区间rev[tree[tree[root][1]][0]] ^= 1; }void in_order(int r) { //中序遍历 if (r == 0) {return ;}push_down(r);in_order(tree[r][0]);if (cnt <= n && cnt >= 1) {if (cnt > 1) {printf(" ");}printf("%d", val[r]);}cnt++;in_order(tree[r][1]);}
};SplayTree spl;int main() {int m, a, b, c;char ch[10];while (~scanf("%d %d", &n, &m) && ~n && ~m) {spl.clear();getchar();while (m--) {scanf("%s", ch);if (ch[0] == 'C') {scanf("%d %d %d", &a, &b, &c);spl.cut(a, b, c);} else {scanf("%d %d", &a, &b);spl.reversal(a, b);}}spl.in_order(spl.root);puts("");}
}

楼下日常更新自己的模板


struct SplayTree {const static int MAX_SIZE = 3e5 + 10;const static int INF = 0x7ffffff;int tree[MAX_SIZE][2], father[MAX_SIZE];  //该点的左右儿子,该点的爸爸节点,int size[MAX_SIZE];                      //该点的子节点数int val[MAX_SIZE];                       //每个点的价值int root, sz;                            //该树的根,该树的节点数int cnt;                                 //中序遍历指针int rev[MAX_SIZE];                       //翻转区间,懒惰更新int sum[MAX_SIZE];                       //求子树的和int lazy[MAX_SIZE];                      //求和,懒惰更新void Treaval(int x) {if (x) {Treaval(tree[x][0]);printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,key = %2d ,sum = %2d\n", x, tree[x][0], tree[x][1], father[x], size[x], val[x], sum[x]);Treaval(tree[x][1]);}}void debug() {printf("%d\n",root);Treaval(root);}void modify(int x) {if (!x) {return ;}rev[x] ^= 1;}//更新节点数void push_up(int r) {size[r] = size[tree[r][0]] + size[tree[r][1]] + 1;sum[r] = sum[tree[r][0]] + sum[tree[r][1]] + val[r];}//lazy更新void push_down(int r) {if (r && rev[r]) {   //翻转swap(tree[r][0], tree[r][1]);modify(tree[r][0]);modify(tree[r][1]);modify(r);}if (r && lazy[r]) {  //更新和sum[tree[r][0]] += lazy[r];sum[tree[r][1]] += lazy[r];lazy[tree[r][0]] += lazy[r];lazy[tree[r][1]] += lazy[r];lazy[r] = 0;}}void new_node(int &r, int fa, int v) {r = ++sz;father[r] = fa;sum[r] = val[r] = v;rev[r] = tree[r][0] = tree[r][1] = 0;}void build(int &rt, int l, int r, int fa) {   //建一棵满的二叉平衡树if (l > r) {return ;}int mid = l + r >> 1;new_node(rt, fa, mid);build(tree[rt][0], l, mid - 1, rt);build(tree[rt][1], mid + 1, r, rt);push_up(rt);}void clear() {sz = root = cnt = 0;size[root] = tree[0][0] = tree[0][1] = rev[0] = father[0] = sum[0] = lazy[0] = 0;memset(rev, 0, sizeof(rev));new_node(root, 0, 0);new_node(tree[root][1], root, 0);size[root] = 1;
// build(tree[tree[root][1]][0], 1, n, tree[root][1]); //建一棵在n+1左边的完全二叉平衡树push_up(tree[root][1]);push_up(root);}void rotate(int x, int k) {   //x是节点,k判断是左旋还是右旋int y = father[x];push_down(y);push_down(x);tree[y][!k] = tree[x][k]; //先变两边的儿子father[tree[x][k]] = y;     //再将x的儿子的爸爸变成yif (father[y]) {          //如果不是root,将y爸爸的儿子也变一下tree[father[y]][tree[father[y]][1] == y] = x;}father[x] = father[y];    //更新x的父亲成y的父亲father[y] = x;            //更新y的父亲成xtree[x][k] = y;           //更新x的儿子成ypush_up(y);}void splay(int x, int r) {    //将x旋转到r的儿子,这里注意是儿子!if (r == 0) {root = x;}push_down(x);while (father[x] != r) {if (father[father[x]] == r) { //zig-steprotate(x, tree[father[x]][0] == x);return ;}int y = father[x];int k = tree[father[y]][0] == y;  //判断上上层是否是左边if (tree[y][k] == x) { // zig-zag-steprotate(x, !k);rotate(x, k);} else {                      // zig-zig-steprotate(y, k);rotate(x, k);}}push_up(x);}int insert(int v) { //插入值,插入完毕后进行splay操作,将插入的位置splay到rootint r = root;while (tree[r][val[r] < v]) {if (val[r] == v) {splay(r, 0);return 0;}push_down(r);r = tree[r][val[r] < v];}new_node(tree[r][val[r] < v], r, v);splay(tree[r][val[r] < v], 0);return 1;}int get_kth(int r, int k) { //获得第k大的rootpush_down(r);int siz = size[tree[r][0]];if (siz == k - 1) {return r;}if (siz >= k) {return get_kth(tree[r][0], k);} else {return get_kth(tree[r][1], k - siz - 1);}}int get_min(int x) {  //获得最小值的位置push_down(x);while (tree[x][0]) {x = tree[x][0];push_down(x);}return x;}int get_max(int x) {  //获得最大值的位置push_down(x);while (tree[x][1]) {x = tree[x][1];push_down(x);}return x;}int get_next(int x) {  //获得比x下标大一点的值push_down(x);int rg = tree[x][1];push_down(rg);if (rg == 0) {return INF;}while (tree[rg][0]) {rg = tree[rg][0];push_down(rg);}return val[rg] - val[x]; //这里返回时可以更改}int get_pre(int x) {   //获得比x下标小一点的值push_down(x);int lt = tree[x][0];push_down(lt);if (lt == 0) {return INF;}while (tree[lt][1]) {lt = tree[lt][1];push_down(lt);}return val[x] - val[lt];}void cut(int a, int b, int c) {     //将[a,b]切断,放在切断后第c个数后面int x = get_kth(root, a);       //这里由于树是[0,n+1]的,所以要找的区间如果是[a,b]则需要将 a-1旋转到根,b+1旋转到a-1的子根,那么b+1的左子树就是要的区间int y = get_kth(root, b + 2);   //又由于从0开始,所以都+1splay(x, 0);splay(y, root);int p = tree[tree[root][1]][0]; //区间树的根tree[tree[root][1]][0] = 0;     //切断push_up(tree[root][1]);push_up(root);                  //更新一下节点数int z = get_kth(root, c + 1);   //切断后就可以找第c位数splay(z, 0);                    //旋转到根int m = get_min(tree[root][1]); //找一下右子树最小的位置splay(m, root);                 //旋转到根的右儿子,那么这个最小的位置的左儿子就是空的了tree[tree[root][1]][0] = p;     //放回去father[tree[tree[root][1]][0]] = tree[root][1];push_up(tree[root][1]);         //更新节点push_up(root);}void reversal(int a, int b) { //[a, b]内区间交换int x = get_kth(root, a);int y = get_kth(root, b + 2);splay(x, 0);    //左区间旋转到根splay(y, root); //右区间旋转到根的左边,那么根的右儿子结点的左儿子节点为所需区间rev[tree[tree[root][1]][0]] ^= 1;}void in_order(int r) { //中序遍历if (r == 0) {return ;}push_down(r);in_order(tree[r][0]);if (cnt >= 1) {printf(" ");}printf("%d", val[r]);cnt++;in_order(tree[r][1]);}int query_sum(int a, int b) {int x = get_kth(root, a);int y = get_kth(root, b + 2);splay(x, 0);splay(y, root);push_up(y);push_up(x);return sum[tree[y][0]];}void add_sum(int a, int v) {int x = get_kth(root, a + 1);splay(x, 0);val[x] += v;push_up(x);}void del() { //这里删除被旋转到root的那个 if (!tree[root][0] || !tree[root][1]) { //如果发现左子树或者右子树是空,直接删除root = tree[root][0] + tree[root][1];father[root] = 0;return ;}int k = get_min(tree[root][1]);            //找到最小的那个splay(k, root);tree[tree[root][1]][0] = tree[root][0];root = tree[root][1];father[tree[root][0]] = root;father[root] = 0;push_up(root);}//这个插入跟之前那个插入不同void insert(int &r, int k, int fa) { //这里插入到最前的那个位置 if (r == 0) {new_node(r, fa, k);return ;}insert(tree[r][0], k, r);push_up(r);}//将某个元素放到最顶部void top_point(int a) {int y = node[a];splay(y, 0);del();insert(root, a, 0);splay(sz, 0);  //听说这步不加会TLE}
};