就是简单的区间翻转操作，打标记就好。代码易懂
#include<bits/stdc++.h> #define INF 2100000001 #define N 100003 using namespace std; int read() { int x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } int root=0,ndnum=0; int fa[N],ch[N][4],key[N],tag[N],siz[N],data[N]; int build(int f,int l,int r)//与线段树的build是有一些区别的 { if(l>r) return 0;//即为空节点 int mid=(l+r)>>1; int now=++ndnum; key[now]=data[mid],fa[now]=f,tag[now]=0;//tag标记 ch[now][0]=build(now,l,mid-1); ch[now][1]=build(now,mid+1,r); siz[now]=siz[ch[now][0]]+siz[ch[now][1]]+1; return now; } int get(int x) { return ch[fa[x]][1]==x; } void update(int x) { siz[x]=siz[ch[x][1]]+siz[ch[x][0]]+1; } void pushdown(int x) { if(x&&tag[x]) { tag[ch[x][0]]^=1; tag[ch[x][1]]^=1; swap(ch[x][1],ch[x][0]); tag[x]=0; } } void rotate(int x) { int old=fa[x],oldf=fa[old]; int which=get(x); ch[old][which]=ch[x][which^1]; fa[ch[old][which]]=old; fa[old]=x;ch[x][which^1]=old; fa[x]=oldf; if(oldf) ch[oldf][ch[oldf][1]==old]=x; update(old);update(x); } void splay(int x,int tar) { for(int f;(f=fa[x])!=tar;rotate(x)) if(fa[fa[x]]!=tar) rotate((get(x)==get(f))?f:x); if(!tar) root=x; } int rank(int x) { int now=root; while(1) { pushdown(now); if(x<=siz[ch[now][0]]) now=ch[now][0]; else { x-=siz[ch[now][0]]+1; if(!x)return now; now=ch[now][1]; } } } void turn(int l,int r) { int x=rank(l); int y=rank(r+2); splay(x,0);splay(y,x); pushdown(root); tag[ch[ch[root][1]][0]]^=1; } void dfs(int x) { pushdown(x); if(ch[x][0])dfs(ch[x][0]); if(key[x]!=-INF&&key[x]!=INF) printf("%d ",key[x]); if(ch[x][1])dfs(ch[x][1]); } int main() { int n=read(),m=read(); for(int i=1;i<=n;++i) data[i+1]=i; data[1]=-INF;data[n+2]=INF;//在反转区间[l~r]的时候，我们可以考虑利用Splay的性质， //将l-1翻转至根节点，再将r+1翻转至根节点的幼儿子为了方便，在1号节点之前n号节点之后加两个节点赋值为-INF和INF //作为虚点，既满足二叉搜索树的性质，又可以让我们在翻转1~n时不会GG root=build(0,1,n+2); for(int i=1;i<=m;++i) { int x=read(),y=read(); turn(x,y); } dfs(root); }
顺便提一嘴的是，关于翻转标记下传时，如果还涉及了其他标记，要考虑影响（见具体题目，比如说还存了最大前缀和最大后缀，那么不仅左右儿子要交换，最大前缀和最大后缀也要进行交换）。
然后我们会发现这道题下标就是对应的值，然而有一些题下标并不是值域，存入key就好了，只是哨兵节点的值可能要变化一下（根据不同题目）。