摘要：
您需要编写一个数据结构来维护有序数组。需要提供以下操作：翻转间隔。例如，如果原始序列为5432154321，翻转间隔为[2,4][2,4]，则结果为5234152341。
您需要写一种数据结构（可参考题目标题），来维护一个有序数列。
其中需要提供以下操作：翻转一个区间，例如原有序序列是 5 4 3 2 15 4 3 2 1，翻转区间是 [2,4][2,4] 的话，结果是 5 2 3 4 15 2 3 4 1。
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+100; const int inf=1e9; int n,m; struct Splay_tree { int fa; int cnt; int ch[2]; int v; int size; int lazy; }t[maxn]; int root,tot; void update (int x) { t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+t[x].cnt; } 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].fa; int z=t[y].fa; int k=(t[y].ch[1]==x); t[z].ch[t[z].ch[1]==y]=x; t[x].fa=z; t[y].ch[k]=t[x].ch[k^1]; t[t[x].ch[k^1]].fa=y; t[x].ch[k^1]=y; t[y].fa=x; update(y); update(x); } void splay (int x,int s) { while (t[x].fa!=s) { int y=t[x].fa; int z=t[y].fa; if (z!=s) (t[z].ch[0]==y)^(t[y].ch[0]==x)?rotate(x):rotate(y); rotate(x); } if (s==0) root=x; } void find (int x) { int u=root; if (!u) return; while (t[u].ch[x>t[u].v]&&x!=t[u].v) u=t[u].ch[x>t[u].v]; splay(u,0); } void ins (int x) { int u=root; int fa=0; while (u&&t[u].v!=x) { fa=u; u=t[u].ch[x>t[u].v]; } if (u) t[u].cnt++; else { u=++tot; if (fa) t[fa].ch[x>t[fa].v]=u; t[u].ch[0]=t[u].ch[1]=0; t[tot].fa=fa; t[tot].v=x; t[tot].cnt=1; t[tot].size=1; } splay(u,0); } int Next (int x,int f) { find(x); int u=root; if (t[u].v>x&&f) return u; if (t[u].v<x&&!f) return u; u=t[u].ch[f]; while (t[u].ch[f^1]) u=t[u].ch[f^1]; return u; } void del (int x) { int lst=Next(x,0); int nxt=Next(x,1); splay(lst,0); splay(nxt,lst); int tt=t[nxt].ch[0]; if (t[tt].cnt>1) { t[tt].cnt--; splay(tt,0); } else t[nxt].ch[0]=0; } int kth (int x) { int u=root; while (t[u].size<x) return 0; while (1) { pushdown(u); int y=t[u].ch[0]; if (x>t[y].size+t[u].cnt) { x-=t[y].size+t[u].cnt; u=t[u].ch[1]; } else if (t[y].size>=x) u=y; else return t[u].v; } } void reverse (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; } void dfs (int u) { pushdown(u); if (t[u].ch[0]) dfs(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]) dfs(t[u].ch[1]); } int main () { scanf("%d%d",&n,&m); for (int i=1;i<=n+2;i++) ins(i); for (int i=1;i<=m;i++) { int l,r; scanf("%d%d",&l,&r); reverse(l,r); } dfs(root); }