AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=3223
通道2：http://codevs.cn/problem/3303/
题目分析：
我们先想想数组怎么操作。
每次O(1)找到区间位置，然后旋转，大概是O(r-l+1)的。
这样太慢了，每次我都将操作进行到底了。可是翻转标记有时候其实不需要每个都去办，因为它们之间还可以互相抵消。
能不能用线段树呢？
找到区间log(n)，标记一下O(1)，可以过？
不行！这个翻转显得与往常处理的线段树题目不一样，因为之前线段树是静态的数轴，但是这个数轴会翻转！
直接根据下标找到的只是数值，不是现在它在数组中的位置。每次怎么找到新的区间位置?
每次去找的时候，将标记下传然后翻转线段树[交换左右节点]好像就行了...
线段树真的可以翻转么？我每个节点的信息岂不是非常混乱！下次再想找到这个区间就不容易了，因为我线段树的数值不满足当初的性质了。
通过刚才的分析，发现这题中的数值其实没有多大作用，只是它特殊的一个标记而已，重要的还是它在序列中的位置，以及如何处理好翻转与查询的关系。
翻转是不能彻底进行的，要用标记且标记不能下传到底，但是在这样的条件下要有一种快速的算法，让我们找到我们需要的区间。
标记让人想到树结构，快速找区间又想到二叉树，于是不妨维护一颗搜索二叉树，其中以这个元素在序列中的位置作为排序的标准。
在每次寻找左右端点时，即使有一些节点的标记还未下传，但是只要这个节点下的子树的元素个数小于当前我的查询值，我就可以跳过它。
反之，就将它的标记下传，并让它的左右子树交换位置，依次往下，直到找到自己需要的那个节点上。
节点到区间的转变怎么实现呢？这边需要Splay()操作了。
首先将l-1转到根节点上来，然后将r+1转到l-1的右节点上。
这样[l,r]就很清晰而且全部存在于一棵子树下了。
有没有觉得这个算法的神奇之处啊？或是说Splay()也可以这样用，标记也可以这样用...Orz
当然这题还有几个地方需要注意，一是当l=1时，需要将排行第0的节点转上来(如果是n的话，你多虚拟一个n+1的节点是可以的)...不可实现啊，
【其实你也可以特判掉，在这种情况下只找r+1翻到顶上(对于n也可以这样特判)】，不过...笔者表示膜别人思路将所有节点的下标前移了一个，所以代码中表现的是将l和r+2进行操作。
二是刚开始建树的话，不仅要注意建到n+2【如果采用特判则是n+1】，也要尽量让它初始就平衡一点哦...
#include<cstdio> #include<cstring> #include<algorithm>using namespace std;inline int in(){int x=0;char ch=getchar();while(ch>'9' || ch<'0') ch=getchar();while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x; }const int maxn=100010;int n,m,rt;struct Node{int sz,f;int l,r;bool mk;void trans(){swap(l,r);} }s[maxn];inline void updata(int x){s[x].sz=s[s[x].l].sz+s[s[x].r].sz+1; }int build(int l,int r){if(l>r) return 0;int mid=(l+r)>>1;s[mid].l=build(l,mid-1);s[mid].r=build(mid+1,r);updata(mid);s[s[mid].l].f=mid,s[s[mid].r].f=mid;return mid; }inline void push_down(int x){if(s[x].mk){s[x].trans();s[s[x].l].mk^=1;s[s[x].r].mk^=1;s[x].mk=0;} }void zig(int x){int y=s[x].f;s[x].f=s[y].f;if(s[y].f){ if(y==s[s[y].f].l) s[s[y].f].l=x;else s[s[y].f].r=x;}s[y].l=s[x].r;if(s[x].r)s[s[x].r].f=y;s[y].f=x,s[x].r=y;updata(y);updata(x); }void zag(int x){int y=s[x].f;s[x].f=s[y].f;if(s[y].f){ if(y==s[s[y].f].l) s[s[y].f].l=x;else s[s[y].f].r=x;}s[y].r=s[x].l;if(s[x].l)s[s[x].l].f=y;s[x].l=y,s[y].f=x;updata(y);updata(x); }void Splay(int x,int gf){int y;while(s[x].f!=gf){y=s[x].f;if(s[y].f==gf){if(x==(s[y].l)) zig(x);else zag(x);}else{int z=s[y].f;if(y==s[z].l){if(x==s[y].l) zig(y),zig(x);else zag(x),zig(x);}else{if(x==s[y].r) zag(y),zag(x);else zig(x),zag(x);}}}if(!gf) rt=x; }int find(int k){int p=rt;if(k>s[p].sz) return 0;while(p){push_down(p);//每访问到一个节点，就将它的标记下传，从这个点到根的路上就都传完了if(k<=s[s[p].l].sz) p=s[p].l;else{k-=s[s[p].l].sz;if(k==1) return p;k--,p=s[p].r;}} }void rev(int l,int r){int a=find(l),b=find(r+2);//这里是找到这两个需要翻转的节点的位置Splay(a,0);Splay(b,a);s[s[b].l].mk^=1; }void print(int x){if(!x) return;push_down(x);print(s[x].l);if(x>1 && x<=n+1) //有几个节点是根据需要虚拟出的，它们不能输出printf("%d ",x-1);print(s[x].r); }int main(){ #ifndef ONLINE_JUDGEfreopen("3223.in","r",stdin);freopen("3223.out","w",stdout); #endifint l,r;n=in();m=in();rt=build(1,n+2);while(m--)l=in(),r=in(),rev(l,r);print(rt);return 0; }
