洛谷 P3391
/*Splay只记模板是很困难的,而且真正运用时易生疏出错,所以必须理解,在看代码前先弄懂
Splay的原理,这篇代码是带注释的Splay模板,题目来自洛谷P3391 ———————————by 520*/
#include<bits/stdc++.h>
#define il inline
using namespace std;
const int N = 100005;
il int gi()
{
int a = 0; char x = getchar(); bool f = 0;
while ((x<'0' || x>'9') && x != '-')x = getchar();
if (x == '-')x = getchar(), f = 1;
while (x >= '0'&&x <= '9')a = a * 10 + x - 48, x = getchar();
return f ? -a : a;
}
int n, m, tot, root, siz[N], fa[N], lazy[N], key[N], tree[N][2], ans[N];
/*root为根节点,siz存储子树节点数,fa存储父节点,lazy是懒惰标记用来标记区间翻转操作,key数组存储原数列,tree为
splay树,ans存储答案*/
il void pushup(int rt) //作用类似与线段树
{
int l = tree[rt][0], r = tree[rt][1]; //pushup作用是将子树的节点个数更新给根节点
siz[rt] = siz[l] + siz[r] + 1;
}
il void pushdown(int now)
{
if (lazy[now]) {
lazy[tree[now][0]] ^= 1;
lazy[tree[now][1]] ^= 1; /*pushdown作用是下放懒惰标记,若某一节点所在子树(即某一区间)被翻转
,则将懒惰标记下放给两个儿子节点,交换左右儿子位置(中序遍历,交换左右儿子后相当于翻转)并对所在子树根节
点的标记清0,*/
swap(tree[now][0], tree[now][1]);
lazy[now] = 0;
}
}
il int getson(int x) { return tree[fa[x]][1] == x; } //getson判断x是其父亲的右儿子还是左儿子
il void rotate(int x) //旋转操作,直接写在一个函数里,可以称为上旋
{
int y = fa[x], z = fa[y], b = getson(x), c = getson(y), a = tree[x][!b]; /*y是x的父节点,z是y的父节点,getson解释过了。
特别解释一下a,a为旋转时需要移动的子树,若x为左儿子则右旋时要将x的右子树移动,同理若x为右儿子则左旋时要
将x的左子树移动,所以这里a=tree[x][!b]*/
if (z)tree[z][c] = x; else root = x; fa[x] = z; /*若z不为根节点,则用x替代y的位置;若z为根节点,则将x变为根节点。*/
if (a)fa[a] = y; tree[y][b] = a; /*若存在要移动的子树a,则把a和y相连,取代原来x的位置*/
tree[x][!b] = y; fa[y] = x; /*!b的原因:若x为左儿子则旋转后y为x的右儿子,若x为右儿子则旋转后y为x的左儿子。记得将y
指向x*/
pushup(y); pushup(x); /*旋转后,对被移动了的y和x更新它们各自的子树节点数*/
}
il void splay(int x, int i)
{
while (fa[x] != i) { //只要x没有旋转到需要的点下面,则一直旋,注意根节点的父亲为虚点0
int y = fa[x], z = fa[y];
if (z == i)rotate(x); //若x的爷爷是i,则只需旋一次
else {
if (getson(x) == getson(y)) { rotate(y); rotate(x); } /*若x和y为相同偏向,则进行Zig-Zig或Zag-Zag操作*/
else { rotate(x); rotate(x); } /*否则进行Zig-Zag或Zag-Zig操作*/
/*注意rotate函数中已经包含了这四种操作情况了*/
}
}
}
il int find(int x) //查找x的位置
{
int now = root; //从根节点往下
while (1) {
pushdown(now); //本次操作要将前面的标记进行翻转
if (tree[now][0] && x <= siz[tree[now][0]])now = tree[now][0]; //若存在左子树且x小于等于左子树的节点数,则x在左子树上
else {
int tmp = (tree[now][0] ? siz[tree[now][0]] : 0) + 1; //往右子树找,+1代表加上这个子树的根节点
if (x == tmp)return now; //若找到了x,返回它的位置
x -= tmp; //否则x减去根节点右子树以外的节点数,这个画图能理解,因为siz值并不是直接的x的值
now = tree[now][1]; //将原来根节点的右儿子赋为新的根节点,继续递归查找x位置
}
}
}
il int build(int l, int r, int rt) //建树过程和线段树类似
{
int now = l + r >> 1;
fa[now] = rt;
key[now] = ans[now]; //key存原数组1到n,准确说是0到n+1,原因是主函数里的预处理
if (l < now)tree[now][0] = build(l, now - 1, now);
if (r > now)tree[now][1] = build(now + 1, r, now);
pushup(now); //记得pushup
return now;
}
il void print(int now) //输出时中序遍历,按左根右输出
{
pushdown(now); //记得要翻转
if (tree[now][0])print(tree[now][0]); //因为中序遍历左根右,所以递归根节点左子树到第一个数的位置
ans[++tot] = key[now]; //回溯时存储答案,注意我们翻转操作的是原数组下标
if (tree[now][1])print(tree[now][1]); //同理递归根节点的右子树
}
int main()
{
n = gi(), m = gi(); int x, y;
for (int i = 1; i <= n + 2; i++)ans[i] = i - 1; /*因为取出操作区间时旋转的是x的前驱和y的后驱,所以预处理时第i个点
存的是i的前驱*/
root = build(1, n + 2, 0);
while (m--)
{
x = gi(), y = gi();
x = find(x), y = find(y + 2); /*查找x的前驱所在的位置,和y后驱所在的位置,因为预处理时ans存的是前趋,
所以直接查找x,而y的后驱变成了y+2*/
splay(x, 0); splay(y, x); /*将x前驱上旋至根节点,y的后驱上旋成根节点右儿子的左子树*/
lazy[tree[tree[root][1]][0]] ^= 1;//经过旋转后,此时根节点的右儿子的左子树就是需要翻转的区间,所以lazy标记
}
print(root);
for (int i = 1; i <= n; i++)printf("%d ", ans[i + 1]); //输出时将前驱还原为原数
return 0;
}
poj 3580&BZOJ 1895
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
const int INF = 1e9;
int n, m;
int ch[maxn][2]; //0做孩子, 1右孩子
int f[maxn]; //每个节点的父亲
int sz[maxn]; //每个节点为根子树的大小
int val[maxn]; //这个节点所表示的值
int cnt[maxn]; //这个节点所表示值的数量
int mi[maxn]; //这个节点子树的最小值
int rev[maxn]; //反转标记
int lazy[maxn]; //延迟标记
int root; // splay的根
int tot; //树所有的节点数量
void Swap(int &x, int &y)
{
x ^= y; y ^= x; x ^= y;
}
int Min(int x, int y)
{
return x < y ? x : y;
}
void update_rev(int x) //更新反转
{
if (!x) return;
Swap(ch[x][0], ch[x][1]);
rev[x] ^= 1; //如果这一层曾经被转过下面就不用转了, 把rev取消了
}
void update_add(int x, int v)
{
if (x) lazy[x] += v, val[x] += v, mi[x] += v;
}
void newnode(int rt, int v, int fa)
{
f[rt] = fa; sz[rt] = 1;
val[rt] = mi[rt] = v;
ch[rt][0] = ch[rt][1] = rev[rt] = lazy[rt] = 0; //加点的时候把所有的信息都更新了
}
void delnode(int rt) //为了回收空间,其实没什么太大的用处
{
f[rt] = val[rt] = sz[rt] = mi[rt] = 0;
ch[rt][0] = ch[rt][1] = rev[rt] = lazy[rt] = 0;
}
void pushup(int x) //跟线段树一样,从下往上不断更新
{
if (!x)return;
sz[x] = 1, mi[x] = val[x];
if (ch[x][0]) sz[x] += sz[ch[x][0]], mi[x] = Min(mi[x], mi[ch[x][0]]); //更新个数跟当前子树最小值
if (ch[x][1]) sz[x] += sz[ch[x][1]], mi[x] = Min(mi[x], mi[ch[x][1]]);
}
void pushdown(int x) //向下传递lazy 跟 rev
{
if (!x) return;
if (lazy[x])
{
update_add(ch[x][0], lazy[x]);
update_add(ch[x][1], lazy[x]);
lazy[x] = 0;
}
if (rev[x])
{
update_rev(ch[x][0]);
update_rev(ch[x][1]);
rev[x] = 0;
}
}
void build(int &rt, int l, int r, int fa) //rt是节点编号,节点的大小代表了两个数位置的相对顺序
{ //一共tot个节点
if (l > r) return;
int mid = (r + l) >> 1;
rt = mid; newnode(rt, val[rt], fa);
build(ch[rt][0], l, mid - 1, rt);
build(ch[rt][1], mid + 1, r, rt);
pushup(rt);
}
void Rotate(int x, int k) // k = 0左旋, k = 1右旋
{
int y = f[x]; int z = f[y];
pushdown(y); pushdown(x);
ch[y][!k] = ch[x][k];
if (ch[x][k]) f[ch[x][k]] = y;
f[x] = z;
if (z) ch[z][ch[z][1] == y] = x;
f[y] = x; ch[x][k] = y;
pushup(y), pushup(x);
}
void splay(int x, int goal)
{
pushdown(x);
while (f[x] != goal)
{
int y = f[x], z = f[y];
//在这里下传翻转标记,在rotate里下传标记可能会使树形改变导致旋转出错
pushdown(z); pushdown(y); pushdown(x);
if (f[y] == goal) Rotate(x, ch[y][0] == x);
else
{
int p = ch[f[y]][0] == y;
if (ch[y][p] == x) Rotate(x, !p), Rotate(x, p);
else Rotate(y, p), Rotate(x, p);
}
}
pushup(x);
if (goal == 0) root = x;
}
//以x为根的子树 的极值点 0 极小 1 极大
int extreme(int x, int k)
{
while (ch[x][k]) x = ch[x][k];
splay(x, 0); //所有操作之后都伸展下
return x;
}
//以节点编号x为根的子树 第k个数的节点编号
int kth(int x, int k)
{
pushdown(x);
if (sz[ch[x][0]] + 1 == k) return x;
else if (sz[ch[x][0]] >= k) return kth(ch[x][0], k);
else return kth(ch[x][1], k - sz[ch[x][0]] - 1);
}
//区间交换
void exchange(int l1, int r1, int l2, int r2)
{
int x = kth(root, l2 - 1), y = kth(root, r2 + 1);
splay(x, 0), splay(y, x);
int tmp_right = ch[y][0]; ch[y][0] = 0; //“剪贴下来”
x = kth(root, l1 - 1), y = kth(root, l1);
splay(x, 0), splay(y, x);
ch[y][0] = tmp_right;
f[tmp_right] = y;
}
//区间翻转
void reversal(int l, int r)
{
int x = kth(root, l - 1), y = kth(root, r + 1);
splay(x, 0); splay(y, x);
update_rev(ch[y][0]); //ch[y][0]就是l-r区间
}
//区间加
void add(int l, int r, int v)
{
int x = kth(root, l - 1), y = kth(root, r + 1);
// cout << 1 <<endl;
splay(x, 0); splay(y, x);
update_add(ch[y][0], v); //ch[y][0]就是l-r区间
}
//在第k个数后插入值为x的节点
void Insert(int k, int x) {
int r = kth(root, k), rr = kth(root, k + 1);
splay(r, 0), splay(rr, r);
newnode(++tot, x, rr); ch[rr][0] = tot; //节点个数增加
for (r = rr; r; r = f[r]) pushdown(r), pushup(r);
splay(rr, 0);
}
//删除第k位置的数
void Delete(int k)
{
splay(kth(root, k - 1), 0);
splay(kth(root, k + 1), root);
delnode(ch[ch[root][1]][0]);
ch[ch[root][1]][0] = 0;
pushup(ch[root][1]);
pushup(root);
}
// 获取区间最大值
//int get_max(int l,int r)
//{
// int x = kth(root,l-1), y = kth(root,r+1);
// splay(x,0); splay(y,x);
// return mx[ch[y][0]];
//}
//获取区间最小值
int get_min(int l, int r)
{
int x = kth(root, l - 1), y = kth(root, r + 1);
splay(x, 0); splay(y, x);
return mi[ch[y][0]];
}
void init(int n)
{
root = 0;
//不断更新的, 不断插入的, 需要一个tot记录插入节点的编号
// tot = 0;
// newnode(++tot, -INF, 0);
// newnode(++tot, INF, root);
// ch[root][1] = tot;
f[0] = sz[0] = ch[0][0] = ch[0][1] = rev[0] = lazy[0] = 0; //rt编号多加两个,处理区间[1,n]
build(root, 1, n, 0);
pushup(root);
}
char s[12];
int main()
{
scanf("%d", &n);
val[1] = val[n + 2] = INF; //多加两个编号0,n+1, 把区间1-n包起来
for (int i = 2; i <= n + 1; i++) scanf("%d", &val[i]);
tot = n + 2;
init(n + 2);
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
int d, l, r;
scanf(" %s", s);
if (s[0] == 'A')
{ //ADD
scanf("%d%d%d", &l, &r, &d);
add(l + 1, r + 1, d);
}
else if (s[0] == 'I')
{ //INSERT
scanf("%d%d", &l, &d);
Insert(l + 1, d);
}
else if (s[0] == 'M')
{ //MIN
scanf("%d%d", &l, &r);
printf("%d\n", get_min(l + 1, r + 1));
}
else if (s[0] == 'D')
{ //DELETE
scanf("%d", &l);
Delete(l + 1);
}
else if (s[3] == 'E')
{ //REVERSE
scanf("%d%d", &l, &r);
reversal(l + 1, r + 1); //增加了1一个节点全体后移一个
}
else
{ //REVOLVE
scanf("%d%d%d", &l, &r, &d);
d = d % (r - l + 1);
if (d) exchange(l + 1, r - d + 1, r - d + 1 + 1, r + 1);
}
}
return 0;
}
更多推荐
某巨文艺平衡树(Splay模板)
发布评论