题目：
我是超链接
题解：
平衡树基本操作----区间翻转
在这个题中，点的排名就是点的值，可以少写一步
代码：
#include <cstdio> #include <iostream> using namespace std; const int N=100005; int ch[N][2],f[N],size[N],delta[N],root,sz,key[N],n; int get(int x){return ch[f[x]][1]==x;} void updata(int now){size[now]=size[ch[now][0]]+size[ch[now][1]]+1;} void pushdown(int now) { if (delta[now]) { swap(ch[now][0],ch[now][1]); delta[ch[now][0]]^=1; delta[ch[now][1]]^=1; delta[now]=0; } } void rotate(int x) { pushdown(f[x]); pushdown(x); int old=f[x],oldf=f[old],which=get(x); f[x]=oldf; if (oldf) ch[oldf][ch[oldf][1]==old]=x; ch[old][which]=ch[x][which^1]; f[ch[x][which^1]]=old; ch[x][which^1]=old; f[old]=x; updata(old); updata(x); } void splay(int x,int to) { for (;f[x]!=to;rotate(x)) if (f[f[x]]!=to) rotate(get(x)==get(f[x])?f[x]:x); if (!to) root=x; } int build(int fa,int l,int r) { if (l>r) return 0; int mid=(l+r)>>1; int now=++sz; key[now]=mid; f[now]=fa; int lch=build(now,l,mid-1); int rch=build(now,mid+1,r); ch[now][0]=lch; ch[now][1]=rch; updata(now); return now; } int find(int x)//位置为x的编号 { int now=root; while (1) { pushdown(now); if (x<=size[ch[now][0]]) now=ch[now][0]; else { x-=size[ch[now][0]]+1; if (!x) return now; now=ch[now][1]; } } } void rev(int l,int r) { l--;r++; if (l==0 && r>n){delta[root]^=1;return;} if (l==0) { int x=find(r); splay(x,0); delta[ch[root][0]]^=1; return; } if (r>n) { int x=find(l); splay(x,0); delta[ch[root][1]]^=1; return; } int x=find(l),y=find(r); splay(x,0); splay(y,x); delta[ch[ch[root][1]][0]]^=1; } void print(int now) { pushdown(now); if (ch[now][0]) print(ch[now][0]); printf("%d ",key[now]); if (ch[now][1]) print(ch[now][1]); } int main() { int m;scanf("%d%d",&n,&m); root=build(0,1,n); for (int i=1;i<=m;i++) { int x,y;scanf("%d%d",&x,&y); rev(x,y); } print(root); }