Splay树（区间添加删除 | 区间翻转）——HDU 3487 Play with Chain

本文主要是介绍Splay树（区间添加删除 | 区间翻转）——HDU 3487 Play with Chain，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

对应HDU题目：点击打开链接

Play with Chain

  
8 2
CUT 3 5 4
FLIP 2 6
-1 -1

  
1 4 3 7 6 2 5 8

题意：

n个数一开始是1~n顺序排列，有两个操作。

CUT（a, b, c）操作表示把第a到第b个数取下放到新组成的第c个数后面；

FLIP（a, b）操作表示把第a到第b个数翻转；

比如样例： n = 8

1   2   3   4   5   6   7   8  

CUT（3,  5,  4）后数列变成 1   2   6   7   3   4   5   8

FLIP（2,  6）后数列变成1   4   3   7   6   2   5   8

问m次操作后的数列为？

思路：

伸展树的基础操作，区间截断，区间翻转。

区间截断：对于CUT（a, b, c）

1）提取区间[a, b]

具体方法：Splay(a - 1, T)，Splay(b +1, T->right)；即把第a - 1个数旋转到根，把第b + 1个数旋转到根的右儿子；那以根的右儿子的左儿子为根的子树就是所有区间[a, b]内的值；把它剪下。

2）把第c个数旋转到根，把第c + 1个数旋转到根的右儿子；那根的右儿子的左儿子肯定是空的。

3）把剪下的子树接在根的右儿子的左儿子。

区间翻转：对于FLIP（a, b）

1）提取区间[a, b]

2）在左儿子做翻转标志（注意不是简单的赋值为1，而是要做异或操作，即原来是1的标记为0，是0的标记为1）

3）在适当的地方加Push_down向下更新（跟线段树区间更新一样）

首先要明白的一点是二叉树结点的信息是最终中序遍历（一定是按下标先后顺序）输出的值，而不是下标的值；那怎样取下标为a的结点呢？

利用每个结点的sz，它表示以该结点为子树的的所有元素个数（T->sz = T->left->sz + T->right->sz + 1）

从根结点p开始

1）如果（左子树的元素个数加上1（1表示p结点） ）sum = p->left->sz + 1；if (sum == a) ，那就找到了，返回p结点

2）sum比a小，说明要往右走（p = p->right）；同时a -= sum；跳到步骤1

3）sum比a大，说明要往左走（p = p->right）；a无需变动；跳到步骤1

怎样书写Push_down函数

就把左右子树对调，然后取消该结点标记，把两棵子树添加标记。

注意：修改时要注意Push_down的地方，注意父亲指针；注意更新sz；用动态的方法时要注意儿子是否为空。

指针型

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAX(x, y) ((x) > (y) ? (x) : (y))typedef struct TREE
{int data;TREE *fa, *l, *r;int sz; //以该结点为根的树的总结点数bool flag; //翻转标记
}Tree;bool space;void Push_down(Tree *T)
{if(NULL == T) return;//左右子树对调if(T->flag){Tree *tmp;tmp = T->r;T->r = T->l;T->l = tmp;T->flag = 0;if(T->l) T->l->flag ^= 1;if(T->r) T->r->flag ^= 1;}
}void Init(Tree *&T, int n)
{int i;bool k = 0;Tree *cur, *pre;for(i = n + 1; i > -1; i--){cur = (Tree *)malloc(sizeof(Tree));cur->data = i;cur->fa = cur->l = cur->r = NULL;cur->sz = 1;cur->flag = 0;if(k){cur->r = pre;pre->fa = cur;cur->sz = pre->sz + 1;}if(!k) k = 1;pre = cur;}T = cur;
}void PreOrder(Tree *T)
{if(NULL == T) return;printf("%d ", T->data);PreOrder(T->l);PreOrder(T->r);
}void MidOrder(Tree *T, int n)
{if(NULL == T) return;Push_down(T);MidOrder(T->l, n);if(T->data > 0 && T->data < n + 1){if(space) printf(" ");else space = 1;printf("%d", T->data);}MidOrder(T->r, n);
}void R_rotate(Tree *x)
{Tree *y = x->fa;Tree *z = y->fa;Tree *k = x->r;int sx = x->sz, sy = y->sz, sk = 0;if(k) sk = k->sz;y->l = k;x->r = y;if(z){if(y == z->l) z->l = x;else z->r = x;}if(k) k->fa = y;y->fa = x;x->fa = z;y->sz = sy - sx + sk;x->sz = sx - sk + y->sz;
}void L_rotate(Tree *x)
{Tree *y = x->fa;Tree *z = y->fa;Tree *k = x->l;int sx = x->sz, sy = y->sz, sk = 0;if(k) sk = k->sz;y->r = k;x->l = y;if(z){if(y == z->r) z->r = x;else z->l = x;}if(k) k->fa = y;y->fa = x;x->fa = z;y->sz = sy - sx + sk;x->sz = sx - sk + y->sz;
}//寻找第x个数的结点
Tree *FindTag(Tree *T, int x)
{if(NULL == T) return NULL;Push_down(T);Tree *p;p = T;int sum = (p->l ? p->l->sz : 0) + 1;while(sum != x && p){if(sum < x){p = p->r;x -= sum;}else p = p->l;Push_down(p);sum = (p->l ? p->l->sz : 0) + 1;}Push_down(p);return p;
}void Splay(int x, Tree *&T)
{Push_down(T);Tree *p, *X, *end, *new_t;end = T->fa;new_t = T;if(end) new_t = T->fa;X = FindTag(new_t, x);while(X->fa != end){p = X->fa;if(end == p->fa){ //p是根结点if(X == p->l) R_rotate(X);else L_rotate(X);break;}//p不是根结点if(X == p->l){if(p == p->fa->l){R_rotate(p); //LLR_rotate(X); //LL}else{R_rotate(X); //RLL_rotate(X);}}else{if(p == p->fa->r){ //RRL_rotate(p);L_rotate(X);}else{ //LRL_rotate(X);R_rotate(X);}}}T = X;
}void CUT(Tree *&T, int a, int b, int c)
{//取[a,b]Splay(a - 1, T);Splay(b + 1, T->r);//剪[a,b]Tree *tmp;tmp = T->r->l;tmp->fa = NULL;T->r->l = NULL;T->r->sz -= tmp->sz;T->sz -= tmp->sz;//移动第c个数到根结点，第c+1个数到根结点右儿子//这样根结点右儿子的左儿子必然为空,就可以把剪掉的放上去Splay(c, T);Splay(c + 1, T->r);//接[a, b]T->r->l = tmp;tmp->fa = T->r;T->r->sz += tmp->sz;T->sz += tmp->sz;
}void FLIP(Tree *&T, int a, int b)
{//取[a,b]Splay(a - 1, T);Splay(b + 1, T->r);//标记T->r->lT->r->l->flag ^= 1;
}void FreeTree(Tree *T)
{if(NULL == T) return;FreeTree(T->l);FreeTree(T->r);free(T);
}int main()
{//freopen("in.txt", "r", stdin);Tree *T;int n, q, a, b, c;char s[6];while(scanf("%d%d", &n, &q), n >= 0 && q >= 0){space = 0;T = NULL;Init(T, n);while(q--){scanf("%s", s);if('C' == s[0]){scanf("%d%d%d", &a, &b, &c);CUT(T, a + 1, b + 1, c + 1);}else{scanf("%d%d", &a, &b);FLIP(T, a + 1, b + 1);}}MidOrder(T, n);printf("\n");FreeTree(T);}return 0;
}

数组型

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define M 300090
#define nul (1<<30)
int data[M];
int Left[M];
int Right[M];
int fa[M];
int sz[M];
bool flag[M];
bool space;void Init()
{int i;for(i = 0; i < M; i++)Left[i] = Right[i] = fa[i] = nul;
}void Push_down(int T)
{if(nul == T) return;if(flag[T]){int tmp = Right[T];Right[T] = Left[T];Left[T] = tmp;flag[T] = 0;if(nul != Left[T]) flag[Left[T]] ^= 1;if(nul != Right[T]) flag[Right[T]] ^= 1;}
}void Create(int &T, int n)
{bool k = 0;int cur, pre;for(cur = n + 1; cur > -1; cur--){data[cur] = cur;sz[cur] = 1;flag[cur] = 0;if(k){Right[cur] = pre;fa[pre] = cur;sz[cur] = sz[pre] + 1;}if(!k) k = 1;pre = cur;}T = pre;
}void InOrder(int T, int n)
{if(nul == T) return;Push_down(T);InOrder(Left[T], n);if(data[T] > 0 && data[T] < n + 1){if(space) printf(" ");else space = 1;printf("%d", data[T]);}InOrder(Right[T], n);
}void PreOrder(int T)
{if(nul == T) return;printf("%d ", data[T]);PreOrder(Left[T]);PreOrder(Right[T]);
}void R_rotate(const int x)
{const int y = fa[x];const int z = fa[y];const int k = Right[x];int sx = sz[x], sy = sz[y], sk = 0;if(nul != k) sk = sz[k];Left[y] = k;Right[x] = y;if(nul != z){if(y == Left[z]) Left[z] = x;else Right[z] = x;}if(nul != k) fa[k] = y;fa[y] = x;fa[x] = z;sz[y] = sy - sx + sk;sz[x] = sx - sk + sz[y];
}void L_rotate(const int x)
{const int y = fa[x];const int z = fa[y];const int k = Left[x];int sx = sz[x], sy = sz[y], sk = 0;if(nul != k) sk = sz[k];Right[y] = k;Left[x] = y;if(nul != z){if(y == Right[z]) Right[z] = x;else Left[z] = x;}if(nul != k) fa[k] = y;fa[y] = x;fa[x] = z;sz[y] = sy - sx + sk;sz[x] = sx - sk + sz[y];
}int FindTag(int T, int x)
{if(nul == T) return nul;Push_down(T);int p = T;int sum = (nul != Left[p] ? sz[Left[p]] : 0) + 1;while(sum != x && nul != p){if(sum < x){p = Right[p];x -= sum;}else p = Left[p];Push_down(p);sum = (nul != Left[p] ? sz[Left[p]] : 0) + 1;}Push_down(p);return p;
}void Splay(int x, int &T)
{Push_down(T);int p, end, new_t;end = fa[T];new_t = T;if(nul != end) new_t = fa[T];x = FindTag(new_t, x);while(end != fa[x]){p = fa[x];if(end == fa[p]){ //p是根结点if(x == Left[p]) R_rotate(x);else L_rotate(x);break;}//p不是根结点if(x == Left[p]){if(p == Left[fa[p]]){R_rotate(p); //LLR_rotate(x); //LL}else{R_rotate(x); //RLL_rotate(x);}}else{if(p == Right[fa[p]]){ //RRL_rotate(p);L_rotate(x);}else{ //LRL_rotate(x);R_rotate(x);}}}T = x;
}void CUT(int &T, int a, int b, int c)
{Splay(a - 1, T);Splay(b + 1, Right[T]);int tmp;tmp = Left[Right[T]];fa[tmp] = Left[Right[T]] = nul;sz[Right[T]] -= sz[tmp];sz[T] -= sz[tmp];Splay(c, T);Splay(c + 1, Right[T]);Left[Right[T]] = tmp;fa[tmp] = Right[T];sz[Right[T]] += sz[tmp];sz[T] += sz[tmp];
}void FLIP(int &T, int a, int b)
{Splay(a - 1, T);Splay(b + 1, Right[T]);flag[Left[Right[T]]] ^= 1;
}int main()
{//freopen("in.txt", "r", stdin);int T;int n, q, a, b, c;char s[6];while(scanf("%d%d", &n, &q), n >= 0 && q >= 0){space = 0;T = nul;Init();Create(T, n);while(q--){scanf("%s", s);if('C' == s[0]){scanf("%d%d%d", &a, &b, &c);CUT(T, a + 1, b + 1, c + 1);}else{scanf("%d%d", &a, &b);FLIP(T, a + 1, b + 1);}}InOrder(T, n);printf("\n");}return 0;
}

这篇关于Splay树（区间添加删除 | 区间翻转）——HDU 3487 Play with Chain的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！