（题目描述略）
伸展树模板题。翻转一个区间，等价于将该区间分成两部分，交换两部分的顺序并分别对两个子区间翻转。实现时，给待翻转的子树标记，懒惰处理，伸展操作时下传标记即可。
设翻转区间 [l, r]，则将排名 l - 1 的节点伸展到根节点，将排名为 r + 1 的节点伸展到根节点的右节点，则以根节点的右节点的左节点为根的子树，必然代表了待翻转的区间。
由于笔者的伸展树的形式是自顶而下，所以在维护子树大小时多有不便。笔者的思想是，由于伸展后根节点的排名已知，故可以自顶而下地维护子树大小，预处理出顶层节点的大小即可。
代码如下：
#include"stdio.h" #define Exchange(a,b) \ { \ typeof(a) __tmp_a=a; \ a=b,b=__tmp_a; \ } struct SPLAY_TREE_NODE *NIL; struct SPLAY_TREE_NODE { int flag,key,size; SPLAY_TREE_NODE *child[2]; SPLAY_TREE_NODE(int k,int s) { flag=0; child[0]=child[1]=NIL; key=k; size=s; } void pushdown() { if(flag==1) { Exchange(child[0],child[1]); flag=0; if(child[0]!=NIL) child[0]->flag^=1; if(child[1]!=NIL) child[1]->flag^=1; } } }; SPLAY_TREE_NODE* Splay(SPLAY_TREE_NODE *now,int rak) { SPLAY_TREE_NODE *Header=new SPLAY_TREE_NODE(0,now->size+1),*next,*SubTree[2]; SubTree[0]=Header; SubTree[1]=Header->child[1]=new SPLAY_TREE_NODE(0,rak); now->pushdown(); while(rak!=now->child[0]->size+1) { int chi=rak<now->child[0]->size+1?0:1; rak-=chi>0?now->child[0]->size+1:0; if((next=now->child[chi])==NIL) break; now->child[chi]=NIL; SubTree[chi]->child[chi]=now; now->size=SubTree[chi]->size-SubTree[chi]->child[1-chi]->size-1; SubTree[chi]=now; now=next; now->pushdown(); } SubTree[0]->child[0]=now->child[1]; SubTree[1]->child[1]=now->child[0]; now->child[0]=Header->child[1]->child[1]; now->child[1]=Header->child[0]; now->size=now->child[0]->size+now->child[1]->size+1; return now; } SPLAY_TREE_NODE* Build(int left,int right) { if(left>=right) return NIL; int middle=(left+right)/2; SPLAY_TREE_NODE *now=new SPLAY_TREE_NODE(middle,right-left); now->child[0]=Build(left,middle); now->child[1]=Build(middle+1,right); return now; } void Output(SPLAY_TREE_NODE *now) { if(now==NIL) return; now->pushdown(); Output(now->child[0]); printf("%d ",now->key); Output(now->child[1]); } int main() { NIL=new SPLAY_TREE_NODE(0,0); NIL->child[0]=NIL->child[1]=NIL; SPLAY_TREE_NODE *stroot; int l,m,n,r; scanf("%d %d",&n,&m); stroot=Build(1,n+1); while(m--) { scanf("%d %d",&l,&r); if(l!=1) if(r!=n) stroot=Splay(stroot,l-1), stroot->child[1]=Splay(stroot->child[1],r-stroot->child[0]->size), stroot->child[1]->child[0]->flag^=1; else stroot=Splay(stroot,l-1), stroot->child[1]->flag^=1; else if(r!=n) stroot=Splay(stroot,r+1), stroot->child[0]->flag^=1; else stroot->flag^=1; } Output(stroot); return 0; }