文艺平衡树（Splay）

题目背景
这是一道经典的Splay模板题——文艺平衡树。

题目描述
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1

输入格式
第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2, \cdots n-1,n)(1,2,⋯n−1,n) m表示翻转操作次数

接下来m行每行两个数 [l,r][l,r] 数据保证 1 \leq l \leq r \leq n1≤l≤r≤n

输出格式
输出一行n个数字，表示原始序列经过m次变换后的结果

输入输出样例
输入 #1复制
5 3
1 3
1 3
1 4
输出 #1复制
4 3 2 1 5
说明/提示
n, m \leq 100000n,m≤100000

题目大意：就是给你一个区间，m次操作，每次反转一个区间，求最后区间的状态。

这道题虽然是splay的模板题，但是我们并不想用splay做（因为不会），于是我们可以考虑用无旋treap来做区间操作。

我们对无旋treap打上懒标记，每次记录一下即可。要注意每次split子树时，先传递懒标记，防止树被分裂之后，懒标记无法正确向下传递。

最后输出答案，一次dfs即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n,m;
int ch[N][2],sz[N],val[N],pri[N],lazy[N],num,root,x,y,z;
inline void push_up(int p){
	sz[p]=sz[ch[p][0]]+sz[ch[p][1]]+1;
}
inline void push_down(int p){
	if(!lazy[p])	return ;	swap(ch[p][0],ch[p][1]);
	lazy[ch[p][0]]^=1;	lazy[ch[p][1]]^=1;	lazy[p]=0;
}
inline int new_node(int v){
	sz[++num]=1; val[num]=v; pri[num]=rand(); return num;
}
void split(int now,int k,int &x,int &y){
	if(!now)	return (void)(x=y=0);
	push_down(now);
	if(k<=sz[ch[now][0]])	y=now,split(ch[now][0],k,x,ch[now][0]);
	else	x=now,split(ch[now][1],k-sz[ch[now][0]]-1,ch[now][1],y);
	push_up(now);
}
int merge(int x,int y){
	if(!x||!y)	return x+y;
	push_down(x);	push_down(y);
	if(pri[x]<pri[y]){
		ch[x][1]=merge(ch[x][1],y);	push_up(x);	return x;
	}else{
		ch[y][0]=merge(x,ch[y][0]);	push_up(y);	return y;
	}
}
inline void reverse(int l,int r){
	split(root,l-1,x,y);	split(y,r-l+1,y,z);
	lazy[y]^=1;	root=merge(merge(x,y),z);
}
void dfs(int x){
	if(!x)	return ;
	push_down(x);
	dfs(ch[x][0]);
	printf("%d ",val[x]);
	dfs(ch[x][1]);
}
signed main(){
	srand((unsigned)time(NULL));
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)	root=merge(root,new_node(i));	
	while(m--){
		int l,r;	scanf("%d %d",&l,&r);	reverse(l,r);
	}
	dfs(root);puts("");
	return 0;
}