传送门 Description
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1
Input
第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数 接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n
Output
输出一行n个数字，表示原始序列经过m次变换后的结果
Sample Input
5 3
1 3
1 3
1 4
Sample Output
4 3 2 1 5
HINT
N,M<=100000
Source
平衡树
splay大法好~ 第二次写splay，手好生啊 相对普通平衡树那道题少了不少操作，但是多了区间翻转操作，所以我们要在原有的基础上增加翻转标记，每次碰到标记就pushdown并且交换左右子树。 但是还有一个问题：在进行翻转操作的时候，由于我们的方法是将 l-1 splay到根上，将 r+1 splay到根的右儿子上，再对 r+1 的左子树进行修改，而当操作范围有1或n的时候，这种方法就失效了，怎么办呢？ 我们可以增增两个虚拟节点，其size值也为1，操作区间[l,r]的时候变为操作[l+1,r+1]就可以了 输出：进行中序遍历，只要是合法的节点就输出该节点的值 ps：蒟蒻在一开始虽然加了虚拟节点但是未给其赋size值，结果每次修改[1,?]的时候要查询第0大的节点，返回的都是null节点，QAQ
CODE：
#include<cstdio> struct node { int num,rev,size; node *fa; node *ch[2]; int getwh() { if(fa->ch[0]==this) return 0;return 1; } void update() { size=ch[0]->size+ch[1]->size+1; } void swap() { node *a=ch[0];ch[0]=ch[1];ch[1]=a; } void pushdown(); void setch(int wh,node *child); }pool[100010],*root,*null; void node::setch(int wh,node *child) { ch[wh]=child; if(child!=null) child->fa=this; update(); } void node::pushdown() { if(!rev) return; if(this==null){rev=0;return;} if(ch[0]!=null) ch[0]->rev^=1; if(ch[1]!=null) ch[1]->rev^=1; rev=0; swap(); } int n,m,x,y,tot; inline node *getnew(int value) { node *now=pool+ ++tot; now->ch[0]=now->ch[1]=now->fa=null; now->num=value; now->size=1; return now; } inline node *build(int l,int r) { int mid=(l+r)>>1; node *now=getnew(mid); if(l<=mid-1) now->setch(0,build(l,mid-1)); if(r>=mid+1) now->setch(1,build(mid+1,r)); return now; } inline void rotate(node *now) { now->pushdown(); node *fa=now->fa,*grand=now->fa->fa; int wh=now->getwh(); fa->setch(wh,now->ch[wh^1]); now->setch(wh^1,fa); now->fa=grand; if(grand!=null) grand->ch[grand->ch[0]==fa?0:1]=now; } inline void splay(node *now,node *tar) { for(;now->fa!=tar;rotate(now)) { now->pushdown(); if(now->fa->fa!=tar) now->getwh()==now->fa->getwh()?rotate(now->fa):rotate(now); } if(tar==null) root=now; } inline node *find(int num) { node *now=root; int rank=0; while(now!=null) { now->pushdown(); int tmp=rank+now->ch[0]->size; if(tmp+1==num) return now; if(num<tmp+1) now=now->ch[0]; else rank=tmp+1,now=now->ch[1]; } } inline void reverse(int l,int r) { node *L=find(l-1),*R=find(r+1); splay(L,null),splay(R,root); R->ch[0]->rev^=1; } void dfs(node *now) { now->pushdown(); if(now->ch[0]!=null) dfs(now->ch[0]); if(now->num!=0&&now->num!=n+1) printf("%d ",now->num); if(now->ch[1]!=null) dfs(now->ch[1]); } int main() { scanf("%d%d",&n,&m); null=pool; null->ch[0]=null->ch[1]=null->fa=null; root=build(0,n+1); while(m--) { scanf("%d%d",&x,&y); x++,y++; reverse(x,y); } dfs(root); return 0; }