Splay模板题
考虑如何把一颗树翻转
把它的左右儿子翻转，左右儿子的左右儿子翻转...直到每个节点都被翻转
一颗树这样转后可以发现树的中序遍历也刚好左右翻转了
所以可以用Splay维护，维护标记也不难，只要每次向下之前都先传一下标记就可以了
注意此时Splay节点的大小关系是他们在序列的位置而不是值
至于提取区间的操作就只要把 l-1 号节点搞到根，把 r+1 号节点搞到根的右儿子
那么整个 l~r 的区间就在 r+1 号节点的左儿子上了
一开始建树可以直接建一个完美的平衡树
因为可能会访问到0号节点或n+1号节点，所以要增加两个虚节点防止越界
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N=1e5+7; inline int read() { register int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } int n,m; int ch[N<<2][2],val[N<<2],fa[N<<2],sz[N<<2],rt; bool rev[N<<2];//翻转标记 inline void pushdown(int &x)//下传标记 { if(rev[x]) { int l=ch[x][0],r=ch[x][1]; if(l) { rev[l]^=1; swap(ch[l][0],ch[l][1]); } if(r) { rev[r]^=1; swap(ch[r][0],ch[r][1]); } rev[x]=0; } } inline void pushup(int &x) { sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1; }//更新节点 inline void rotate(int x,int &k)//伸展 { int y=fa[x],z=fa[y],d=(ch[y][1]==x); if(y==k) k=x; else ch[z][(ch[z][1]==y)]=x; fa[x]=z; fa[y]=x; fa[ch[x][d^1]]=y; ch[y][d]=ch[x][d^1]; ch[x][d^1]=y; pushup(y); pushup(x); } inline void splay(int x,int &k) { while(x!=k) { int y=fa[x],z=fa[y]; if(y!=k) { if( (ch[y][1]==x)^(ch[z][1]==y) ) rotate(x,k); else rotate(y,k); } rotate(x,k); } } void build(int l,int r,int f)//建树 { int mid=l+r>>1; if(mid>l) build(l,mid-1,mid); if(mid<r) build(mid+1,r,mid); fa[mid]=f; ch[f][mid>f]=mid; pushup(mid); } inline int find(int k)//找到排名第k的数 { int now=rt; while(233) { pushdown(now);//每次向下之前先下传标记 if(ch[now][0]&&k<=sz[ch[now][0]]) { now=ch[now][0]; continue; } if(k>sz[ch[now][0]]+1) { k-=sz[ch[now][0]]+1; now=ch[now][1]; continue; } return now; } } inline void rever(int l,int r)//翻转 { int now=find(r+2);//注意r+2,因为有虚节点 splay(find(l/*注意l不用减1因为有虚节点*/),rt); splay(now,ch[rt][1]); now=ch[now][0]; swap(ch[now][0],ch[now][1]); rev[now]^=1;//翻转并打上标记 } void print(int x)//中序遍历并输出 { pushdown(x);//先传标记再向下 if(ch[x][0]) print(ch[x][0]); if(val[x]>1&&val[x]<n+2)printf("%d ",val[x]-1); if(ch[x][1]) print(ch[x][1]); } int main() { n=read(); m=read(); for(int i=1;i<=n+2;i++) val[i]=i;//新增一个最大和最小的虚节点 rt=(1+n+2)>>1; build(1,n+2,0); int a,b; for(int i=1;i<=m;i++) { a=read(); b=read(); rever(a,b); } print(rt); return 0; }