题目背景
这是一道经典的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次变换后的结果
#includeusing namespace std;const int maxn = 100000+5;const int inf = 2000000008;int root,tot,ch[maxn][2],lazy[maxn],fa[maxn],siz[maxn];int n,m;struct Splay{ void init(int t, int par = 0){ ch[t][0] = ch[t][1] = 0; fa[t] = par; } void up(int t){ siz[t] = siz[ch[t][1]] + siz[ch[t][0]] + 1; } void down(int t){ if(!lazy[t])return; swap(ch[t][0], ch[t][1]); lazy[ch[t][0]] ^= 1; lazy[ch[t][1]] ^= 1; lazy[t] = 0; } void init(){ init(0, 0); tot = root = 0; } int find( int x, int t = root){ down(t); if(!x)return t; if(x > siz[ch[t][0]]+1)return find(x - siz[ch[t][0]] - 1, ch[t][1]); if(x == siz[ch[t][0]] + 1)return t; return find(x, ch[t][0]); } void rotate(int x, int d){ int y = fa[x]; down(y),down(x); ch[y][d^1] = ch[x][d]; if(ch[x][d])fa[ch[x][d]] = y; fa[x] = fa[y]; if(fa[y]){ if(y == ch[fa[y]][d])ch[fa[y]][d] = x; else ch[fa[y]][d^1] = x; } ch[x][d] = y;fa[y] = x; up(y),up(x); } void splay(int x, int targrt){ while(fa[x] != targrt){ int y = fa[x]; if(x == ch[y][0]){ if(targrt != fa[y]&& y == ch[fa[y]][0]) rotate(y, 1); rotate(x, 1); } else { if(targrt != fa[y]&& y == ch[fa[y]][1]) rotate(y, 0); rotate(x, 0); } } if(!targrt)root = x; } int build(int f, int l, int r){ if(l > r)return 0; int m = (l + r) >> 1; init(m, f); ch[m][0] = build(m, l, m-1); ch[m][1] = build(m, m+1, r); up(m); return m; } void rev(int l, int r){ int L = find(l); int R = find(r+2); splay(L, 0); splay(R, L); //int x = ch[R][0]; int x = ch[ch[root][1]][0]; lazy[x] ^= 1; }}Tr;int main(){ scanf("%d%d",&n,&m); root = Tr.build(0, 1, n+2); while(m--){ int opt,x; scanf("%d%d",&opt,&x); Tr.rev(opt, x); } for(int i = 1; i <= n; i++)printf("%d ",Tr.find(i+1)-1); return 0;}