学习笔记：splay树(2)

1.题目描述

传送门：here

大意：给你一个序列，让你每次翻转区间\([l,r]\)，并且输出最后的区间

2.思路

1.暴力

每次暴力翻转区间 时间复杂度\(O(n^2)\) 妥妥T

2.平衡树

考虑怎么用splay实现

我们知道平衡树的特性：不管怎么树旋转 它的中序遍历一定是不变的 而且\(BST\)的中序遍历一定是从小到大的

思考如何利用这个性质

翻转区间是什么？

不就是在一段区间遍历中，从左根右变成右根左

这样折腾太麻烦，不如直接交换左右子树位置

怎么找到那一段区间的子树呢？

回忆一下是怎么删除节点的

把前驱翻转到根，后继翻转到根的右节点，那么根节点的右子树的左子树就是要找的点

同理，翻转区间\([l,r]\)，我们把\(l-1\)翻转到根，把\(r+1\)翻转到右子树，此时左子树为对应区间

因为一开始直接给定了序列，可以一开始就建出一棵完美平衡树

同样要插入最小和最大

还有些优化就是为了减少时间复杂度打上懒标记

其他就没什么了

注意：此时满足的是编号的\(BST\) 而不是\(val\)的\(BST\)

Code:

#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int n,m,a[MAXN];
int tot,root;
int size[MAXN],fa[MAXN],val[MAXN];
int tr[MAXN][2],lz[MAXN];
void Pushup(int x)
{
	size[x]=size[tr[x][0]]+size[tr[x][1]]+1;
}
void Pushdown(int x)
{
	if(!lz[x]) return;
	swap(tr[x][0],tr[x][1]);
	lz[tr[x][1]]^=1;
	lz[tr[x][0]]^=1;
	lz[x]=0;
}
int chk(int x)
{
	return tr[fa[x]][1]==x;
}
void rotate(int x)
{
	int y=fa[x],z=fa[y],k=chk(x),w=tr[x][k^1];
	tr[y][k]=w;fa[w]=y;
	tr[z][chk(y)]=x;fa[x]=z;
	tr[x][k^1]=y;fa[y]=x;
	Pushup(y);
	Pushup(x);
}
void splay(int x,int goal)
{
	while(fa[x]!=goal)
	{
		int y=fa[x];
		int z=fa[y];
		if(z!=goal)
			if(chk(x)^chk(y)) rotate(x);
			else rotate(y);
		rotate(x);
	}
	if(!goal) root=x;
}
int build(int l,int r,int f)
{
	if(l>r) return 0;
	int now=++tot;
	fa[now]=f;
	int mid=(l+r)/2;
	val[now]=a[mid];
	tr[now][0]=build(l,mid-1,now);
	tr[now][1]=build(mid+1,r,now);
	Pushup(now);
	return now;
}
int kth(int k)
{
	int now=root;
	while(1)
	{
		Pushdown(now);
		if(tr[now][0]&&k<=size[tr[now][0]])
			now=tr[now][0];
		else if(k>size[tr[now][0]]+1)
		{
			k-=size[tr[now][0]]+1;
			now=tr[now][1];
		}
		else
			return now;
	}
}
void print(int now)
{
	Pushdown(now);
	if(tr[now][0]) print(tr[now][0]);
	if(val[now]>=1&&val[now]<=n)cout<<val[now]<<" "; 
	if(tr[now][1]) print(tr[now][1]); 
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n+1;i++)
		a[i+1]=i;
	root=build(1,n+2,0);
	for(int i=1;i<=m;i++)
	{
		int l,r;
		cin>>l>>r;
		l=kth(l),r=kth(r+2);
		splay(l,0);
		splay(r,l);
		lz[tr[r][0]]^=1;
	}
	print(root);
	return 0;
}