题目背景
这是一道经典的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 n 1≤l≤r≤n
输出格式：
输出一行n个数字，表示原始序列经过m次变换后的结果
输入输出样例
输入样例#1：
5 3
1 3
1 3
1 4
输出样例#1：
4 3 2 1 5
说明
(n, m leq 100000)
思路见注释。
代码：
#include<iostream>
#include<cstdio>
#define maxn 200001
using namespace std;
inline int qread() {
char c=getchar();int num=0,f=1;
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) num=num*10+c-'0';
return num*f;
}
struct tree {
int ch[2];
int ff,v,size,lazy;
void init(int x,int fa) {
ff=ch[0]=ch[1]=0;
size=1;
v=x;
ff=fa;
}
} t[maxn];
int n,root,m,tot;
inline void pushup(int x) {
t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+1;
}
inline void pushdown(int x) {
if(t[x].lazy) {
t[t[x].ch[0]].lazy^=1;
t[t[x].ch[1]].lazy^=1;
t[x].lazy=0;
swap(t[x].ch[0],t[x].ch[1]);
}
}
void rotate(int x) {
int y=t[x].ff; //x的父亲 。
int z=t[y].ff; //x的爷爷。
int k=t[y].ch[1]==x; //x是y的哪一个儿子。
t[z].ch[t[z].ch[1]==y]=x; //z的原来的y的位置变为x。
t[x].ff=z; //x的父亲变为z。
t[y].ch[k]=t[x].ch[k^1]; //x的与x原来在y的相对的那个儿子变成y的儿子。
t[t[x].ch[k^1]].ff=y; //更新父节点。
t[x].ch[k^1]=y; //x的与x原来相对位置的儿子变成y。
t[y].ff=x; //更新父节点。
pushup(y);
pushup(x);
}
inline void splay(int x,int goal) { //将x转为goal的儿子，若x为0，则旋转为根。
while(t[x].ff!=goal) { //一直转到x成为goal的儿子。
int y=t[x].ff,z=t[y].ff; //父节点祖父节点。
if(z!=goal)
(t[z].ch[0]==y)^(t[y].ch[0]==x)?rotate(x):rotate(y); //分情况。
rotate(x); //无论什么情况都要最后旋转x。
}
if(!goal) //若goal为0，则更新x为根节点。
root=x;
}
inline void insert(int x) {
int u=root,ff=0;
while(u) ff=u,u=t[u].ch[x>t[u].v];
u=++tot;
if(ff) t[ff].ch[x>t[ff].v]=u;
t[u].init(x,ff);
splay(u,0);
}
inline int kth(int k) {
int u=root;
while(1) {
pushdown(u);
if(t[t[u].ch[0]].size>=k) u=t[u].ch[0];
else if(t[t[u].ch[0]].size+1==k) return u;
else k-=t[t[u].ch[0]].size+1,u=t[u].ch[1];
}
}
void write(int u) {
pushdown(u);
if(t[u].ch[0]) write(t[u].ch[0]);
if(t[u].v>1&&t[u].v<n+2) printf("%d ",t[u].v-1);
if(t[u].ch[1]) write(t[u].ch[1]);
}
inline void work(int l,int r) {
l=kth(l);
r=kth(r+2);
splay(l,0);
splay(r,l);
t[t[t[root].ch[1]].ch[0]].lazy^=1;
}
int main() {
n=qread(),m=qread();
for(int i=1; i<=n+2; ++i) insert(i);
while(m--) {
int l=qread(),r=qread();
work(l,r);
}
write(root);
printf("
");
return 0;
}