谁都能学会的文艺平衡树

文艺平衡树

为什么要叫这个名字？因为翻转很文艺吗...

给你一个序列，每次进行区间翻转，要求最终得到的序列.

分析

正如它的名字一样，我们用FHQtreap来解决这个问题。

既然实现区间翻转了，那BST性质是否就被破坏掉了呢？

非也，还记得学习BST时我们提到了，二叉搜索树的中序遍历就是把序列从小到大排序的结果，

那么在这里就可以把顺序当作权值，维护这棵平衡树，从而实现区间操作。

具体怎么做呢？参照平衡树找第k小的做法，把顺序前l小（就是权值前l小）个元素分裂出来，

再从分裂出来的另一棵树中找到l到r的这部分分裂出来，再对这棵树进行操作就行了。

回到本题，要求的区间操作是翻转，把整棵树所有节点的左右儿子互换当然可以达到翻转的效果，但是复杂度达到了恐怖的O（n），这怎么能行？！

回想线段树区间修改的做法，对了！可以打上一个lazytag，这样在用上了的时候进行下传就可以了。

代码实现

#include<bits/stdc++.h>

using namespace std;
mt19937 rnd(233);
const int maxn=1e6 + 5;
struct node{
	int l,r,val,siz,key;
	bool lazy;
}f[maxn];
int root,tot;
inline int newnode(int val){
	f[++tot].val=val;
	f[tot].siz=1;
	f[tot].key=rnd();
	return tot;
}
inline void update(int p){
	f[p].siz=f[f[p].l].siz+f[f[p].r].siz+1;
}
inline void pushdown(int p){
	swap(f[p].l,f[p].r);
	f[f[p].l].lazy^=1;
	f[f[p].r].lazy^=1;
	f[p].lazy=0;
}
inline void split(int p,int size,int &x,int &y){
	if(!p)x=y=0;
	else {
		if(f[p].lazy)pushdown(p);
		if(f[f[p].l].siz<size){
			x=p;
			split(f[p].r,size-f[f[p].l].siz-1,f[p].r,y);
		}
		else {
			y=p;
			split(f[p].l,size,x,f[p].l);
		}
		update(p);
	}
}
inline int merge(int x,int y){
	if(!x||!y)return x+y;
	if(f[x].key<f[y].key){
		if(f[x].lazy)pushdown(x);
		f[x].r=merge(f[x].r,y);
		update(x);
		return x;
	}
	else {
		if(f[y].lazy)pushdown(y);
		f[y].l=merge(x,f[y].l);
		update(y);
		return y;
	}
}
void rev(int l,int r){
	int x,y,z;
	split(root,l-1,x,y);
	split(y,r-l+1,y,z);
	f[y].lazy^=1;
	root=merge(merge(x,y),z);
}
void ldr(int p){
	if(!p)return ;
	if(f[p].lazy)pushdown(p);
	ldr(f[p].l);
	printf("%d ",f[p].val);
	ldr(f[p].r);
}
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int main(){
	int n=read(),m=read();
	for(int i=1;i<=n;i++){
		root=merge(root,newnode(i));
	}
	for(int i=1;i<=m;i++){
		int l=read(),r=read();
		rev(l,r);
	}
	ldr(root);
}

写在后面

既然支持了区间操作和lazytag，那么这种平衡树就可以支持线段树的所有操作，甚至还有线段树不能实现的操作！但是常数略大略大...