【分析】注：CodeVS上的原题解。
这道题可以用splay做：
区间操作很自然的会想到懒标记。
定义F(i,j)为对i到j进行一次翻转。
我们发现对于某个区间[i,j]的翻转操作有F(i,j)=F(i,n)->F(n-j+i,n)->F(i,n);
而F(i,n)操作很容易实现(splay i的前驱到根，右子树即是目标区间，事实上将i splay根，j splay到i右儿子也可)。
然后放标记，意为将子树中所有节点的左右子树互换。
在Rotate，查找时记得push即可。
最后dfs输出。
【小结】
①对于静态区间的问题，都想想能不能转化为前缀或者后缀。
②Splay旋到根的作用，两个节点旋到指定位置的作用。
split. count. etc.
【代码】
<span style="font-size:18px;">#include <cstdio>#include <cstring>#include <cstdlib>using namespace std;const int N=100010;int n,m;struct Splay{int f,l,r;int size,tag;}tr[N];int tt,rt;inline void push_up(int now){tr[now].size=tr[tr[now].l].size+tr[tr[now].r].size+1;}int ins(int &now,int w){int t;if (!now) tr[t=now=++tt].size=1;elseif (w<=now){t=ins(tr[now].l,w);tr[tr[now].l].f=now;}else{t=ins(tr[now].r,w);tr[tr[now].r].f=now;}push_up(now);return t;}inline void rr(int now){int t=tr[now].l;tr[tr[now].f].l==now?tr[tr[now].f].l=t:tr[tr[now].f].r=t;tr[t].f=tr[now].f;tr[now].l=tr[t].r;tr[tr[t].r].f=now;tr[now].size=tr[now].size-tr[t].size+tr[tr[t].r].size;tr[t].r=now;tr[now].f=t;tr[t].size=tr[tr[t].l].size+tr[tr[t].r].size+1;}inline void rl(int now){int t=tr[now].r;tr[tr[now].f].l==now?tr[tr[now].f].l=t:tr[tr[now].f].r=t;tr[t].f=tr[now].f;tr[now].r=tr[t].l;tr[tr[t].l].f=now;tr[now].size=tr[now].size-tr[t].size+tr[tr[t].l].size;tr[t].l=now;tr[now].f=t;tr[t].size=tr[tr[t].l].size+tr[tr[t].r].size+1;}void splay(int now){int f,t,w1,w2;for (;tr[now].f;){f=tr[now].f,t=tr[f].f;w1=(tr[f].l==now?0:1);if (!t)!w1?rr(f):rl(f);else{w2=(tr[t].l==f?0:1);if (w1==w2){!w2?rr(t):rl(t);!w1?rr(f):rl(f);}else{!w1?rr(f):rl(f);!w2?rr(t):rl(t);}}}rt=now;}inline int read(void){int s=0,f=1; char c=getchar();for (;c<'0'||c>'9';c=getchar()) if (c=='-') f=-1;for (;'0'<=c&&c<='9';c=getchar()) s=(s<<1)+(s<<3)+c-'0';return s*f;}inline void push_down(int now){if (!tr[now].tag) return;tr[now].l^=tr[now].r^=tr[now].l^=tr[now].r;tr[tr[now].l].tag^=1;tr[tr[now].r].tag^=1;tr[now].tag=0;}int find(int now,int size){push_down(now);if (size<=tr[tr[now].l].size) return find(tr[now].l,size);size-=tr[tr[now].l].size;return size==1?now:find(tr[now].r,size-1);}void dfs(int now){if (!now) return;push_down(now);dfs(tr[now].l);if (now^n+1) printf("%d ",now);dfs(tr[now].r);}int main(void){n=read(),m=read();for (int i=1;i<=n;i++) splay(ins(rt,i));splay(ins(rt,0));int x,y;for (int i=1;i<=m;i++){x=read(),y=read();splay(find(rt,x)),tr[tr[rt].r].tag^=1;splay(find(rt,n-y+x)),tr[tr[rt].r].tag^=1;splay(find(rt,x)),tr[tr[rt].r].tag^=1;}dfs(rt);printf("\n");return 0;}</span>
版权声明：本文为博主原创文章，未经博主允许不得转载。
，愚者用肉体监视心灵，智者用心灵监视肉体
