题目背景
这是一道经典的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
splay区间翻转每个区间逐层翻转然后合并
当然我们并不需要每次翻转就直接翻到底，而是打一个标记，类似于线段树，在查询的时候在随着查询的深入翻转
#include<cstdio> #include<iostream> using namespace std; #define N 100005 int n,m; struct node{ int siz,fa,ch[2];//0zuo,1you; bool rev; }tr[N]; int root; void push_down(int rt) { if(tr[rt].rev) { swap(tr[rt].ch[1],tr[rt].ch[0]); tr[rt].rev=0; tr[tr[rt].ch[0]].rev^=1;tr[tr[rt].ch[1]].rev^=1; } } void pushup(int rt) { tr[rt].siz=tr[tr[rt].ch[0]].siz+tr[tr[rt].ch[1]].siz+1; return; } int find(int rt,int x) { if(rt==0)return 0; push_down(rt); if(x<=tr[tr[rt].ch[0]].siz)return find(tr[rt].ch[0],x); if(x==tr[tr[rt].ch[0]].siz+1)return rt; return find(tr[rt].ch[1],x-tr[tr[rt].ch[0]].siz-1); } void rotate(int &rt,int x) { int y=tr[x].fa,q=tr[y].fa; bool dy=tr[y].ch[1]==x,dz=tr[q].ch[1]==y; push_down(y); if(rt==y)rt=x,tr[x].fa=q; else tr[q].ch[dz]=x,tr[x].fa=q; tr[y].ch[dy]=tr[x].ch[dy^1],tr[tr[x].ch[dy^1]].fa=y; tr[x].ch[dy^1]=y,tr[y].fa=x; pushup(y); return ; } void splay(int &rt,int x) { push_down(x); while(rt!=x) { int y=tr[x].fa;int q=tr[y].fa; if(y!=rt) { if(tr[y].ch[1]==x^tr[q].ch[1]==y)rotate(rt,x); else rotate(rt,y); } rotate(rt,x); } pushup(x); return; } void print(int rt) { if(rt==0)return; push_down(rt); print(tr[rt].ch[0]); if(rt>1&&rt<n+2)printf("%d ",rt-1); print(tr[rt].ch[1]); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n+2;i++) { tr[i].siz=n+3-i;tr[i].fa=i-1;tr[i].ch[1]=i+1; } tr[n+2].ch[1]=0,root=1; while(m--) { int l,r; scanf("%d%d",&l,&r); splay(root,find(root,l)); splay(tr[root].ch[1],find(root,r+2)); tr[tr[tr[root].ch[1]].ch[0]].rev^=1; } print(root); return 0; }