题目大意：
实现一个数据结构支持区间翻转操作共$n(nleq100000)$次。
思路：
Splay维护区间。
对于区间$[l,r]$的翻转可以先将$l-1$旋转到根，再把$r+1$旋转到根的右子结点，此时根结点的右子结点的左子树就是需要翻转的区间。注意翻转过后结点的权值可能不满足二叉搜索树的性质，也不需要满足二叉搜索树的性质。
1 #include<cstdio> 2 #include<cctype> 3 #include<algorithm> 4 inline int getint() { 5 register char ch; 6 while(!isdigit(ch=getchar())); 7 register int x=ch^'0'; 8 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 9 return x; 10 } 11 const int N=100003; 12 int n,ans[N]; 13 class SplayTree { 14 private: 15 int val[N],par[N],size[N],ch[N][2]; 16 bool rev[N]; 17 int sz,new_node(const int &x) { 18 val[++sz]=x; 19 size[sz]=1; 20 return sz; 21 } 22 void push_down(const int &p) { 23 if(!rev[p]) return; 24 std::swap(ch[p][0],ch[p][1]); 25 rev[ch[p][0]]^=1; 26 rev[ch[p][1]]^=1; 27 rev[p]=0; 28 } 29 void push_up(const int &p) { 30 size[p]=size[ch[p][0]]+size[ch[p][1]]+1; 31 } 32 void rotate(const int &x) { 33 const int y=par[x],z=par[y]; 34 push_down(y),push_down(x); 35 const bool b=x==ch[y][0]; 36 par[ch[x][b]=par[ch[y][!b]=ch[x][b]]=y]=x; 37 if(par[x]=z) par[ch[z][ch[z][1]==y]=x]=z; 38 push_up(y),push_up(x); 39 } 40 void splay(int x,const int &goal) { 41 for(register int y=par[x],z=par[y];y!=goal;rotate(x),z=par[y=par[x]]) { 42 if(z!=goal) rotate((x==ch[y][0])^(y==ch[z][0])?x:y); 43 } 44 if(!goal) root=x; 45 } 46 public: 47 int root; 48 void insert(const int &x) { 49 int y=root; 50 while(ch[y][x>val[y]]) y=ch[y][x>val[y]]; 51 par[ch[y][x>val[y]]=new_node(x)]=y; 52 splay(sz,0); 53 } 54 void build(const int &n) { 55 for(register int i=0;i<=n+1;i++) insert(i); 56 } 57 int find(int x) { 58 for(register int y=root;;y=ch[y][size[ch[y][0]]<x]) { 59 push_down(y); 60 if(par[y]&&y==ch[par[y]][1]) x-=size[ch[par[y]][0]]+1; 61 if(size[ch[y][0]]==x) return y; 62 } 63 } 64 void reverse(const int &l,const int &r) { 65 splay(find(l-1),0); 66 splay(find(r+1),root); 67 rev[ch[ch[root][1]][0]]^=1; 68 } 69 void dfs(const int &p) { 70 push_down(p); 71 if(ch[p][0]) dfs(ch[p][0]); 72 if(val[p]&&val[p]<=n) ans[++ans[0]]=val[p]; 73 if(ch[p][1]) dfs(ch[p][1]); 74 } 75 }; 76 SplayTree t; 77 int main() { 78 t.build(n=getint()); 79 for(register int i=getint();i;i--) { 80 const int l=getint(),r=getint(); 81 t.reverse(l,r); 82 } 83 t.dfs(t.root); 84 for(register int i=1;i<=n;i++) printf("%d ",ans[i]); 85 return 0; 86 }