CODEVS 1743 翻转卡片
小A将N张卡片整齐地排成一排，其中每张卡片上写了1~N的一个整数，每张卡片上的数各不相同。
比如下图是N=5的一种情况：3 4 2 1 5
接下来你需要按小A的要求反转卡片，使得左数第一张卡片上的数字是1。操作方法：令左数第一张卡片上的数是K，如果K=1则停止操作，否则将左数第1~K张卡片反转。
第一次(K=3)反转后得到：2 4 3 1 5
第二次(K=2)反转后得到：4 2 3 1 5
第三次(K=4)反转后得到：1 3 2 4 5
可见反转3次后，左数第一张卡片上的数变成了1，操作停止。
你的任务是，对于一种排列情况，计算要反转的次数。你可以假设小A不会让你操作超过100000次。
输入描述 Input Description
第1行一个整数N；
第2行N个整数，为1~N的一个全排列。
输出描述 Output Description
仅1行，输出一个整数表示要操作的次数。
如果经过有限次操作仍无法满足要求，输出-1。
样例输入 Sample Input
5
3 4 2 1 5
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
0<N≤300,000。
裸的区间翻转splay，个人感觉splay的精妙之处在于lazy时交换左右儿子，隐性的完成了区间翻转。
在旋转[l,r]时，我们将l-1旋转至根，r+1旋转至根的右儿子。这样根的右儿子的左边各后代就是要旋转的区间了，根据二叉搜素树的性质，把树上的每个点的左右儿子换一换，就完成了旋转。（本来比他大的变小了，比他小的变比他大了），顺便还维护了一下平衡树的时间复杂度O（nlogn）(摊还分析)。
上代码（有很多细节要注意）我们翻转[l,r]区间时,将l-1转到根，r+1转到根的右节点
所以我们要加进去几个虚点，防止超边界~~
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; #define N 300005 int c[N][2],val[N],pre[N],size[N],rt,a[N],tag[N]; void update(int k) { size[k]=size[c[k][0]]+size[c[k][1]]+1; } void build(int l,int r,int fa) { //cout<<"build"<<endl; if(l>r) return; int mid=(l+r)>>1; if(mid<fa) c[fa][0]=mid;else c[fa][1]=mid; val[mid]=a[mid],pre[mid]=fa; if(l==r) { size[mid]=1; return ; } build(l,mid-1,mid);build(mid+1,r,mid); //size[mid]=size[c[mid][0]]+size[c[mid][1]]; update(mid); } void rotate(int x,int& k) { //cout<<"rotate"<<x<<' '<<k<<endl; int y=pre[x],z=pre[y],l,r; if(c[y][0]==x) l=0,r=1;else l=1,r=0; if(y==k) k=x;else { if(c[z][0]==y) c[z][0]=x;else c[z][1]=x; } pre[x]=z;pre[y]=x; pre[c[x][r]]=y; c[y][l]=c[x][r]; c[x][r]=y; update(y);update(x); } void splay(int x,int &k) { //cout<<"splay"<<endl; while(x!=k) { int y=pre[x],z=pre[y]; if(y!=k) { if(c[y][0]==x^c[z][0]==y) { rotate(x,k); }else { rotate(y,k); } } rotate(x,k); } } void push_down(int k) { tag[k]=0; swap(c[k][0],c[k][1]); tag[c[k][0]]^=1;tag[c[k][1]]^=1; } int find(int k,int rk) { if(tag[k]) push_down(k); if(size[c[k][0]]+1==rk) return k; if(size[c[k][0]]>=rk) return find(c[k][0],rk);else return find(c[k][1],rk-size[c[k][0]]-1); } void rever(int l,int r) { int x=find(rt,l);int y=find(rt,r+2); //cout<<"rever"; //cout<<x<<' '<<y<<endl; splay(x,rt);splay(y,c[rt][1]); tag[c[y][0]]^=1; } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i+1]); build(1,n+2,0); rt=(n+3)>>1; int ans=0; while(val[find(rt,2)]!=1) { ans++; rever(1,val[find(rt,2)]); if(ans>100000) { cout<<-1<<endl; return 0; } } cout<<ans<<endl; }