【codevs1743】反转卡片
题目描述 Description
【dzy493941464|yywyzdzr原创】
小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。
题解：两种方法，rope，十分简单的，c++#include<ext/rope>可持久化平衡树，。
splay，区间旋转在其实就想到了splay吧，每次lg，常数大一些。
红色代表虚点，黑色代表实点，先翻转成这个样子，然后对于根的右子树的左子树的根打上旋转标记
即可。
旋转标记
代码注释了不少
rope代码
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<ext/rope>
#include<ext/hash_map> #define N 300007
using namespace std;
using namespace __gnu_cxx;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if (ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,ans;
int a[N];
rope<int>s1,s2,t1,t2; void spin(int x)
{
t1=s1.substr(,x);
t2=s2.substr(n-x,x);//后者是长度
s1=t2+s1.substr(x,n-x);
s2=s2.substr(,n-x)+t1;
}
int main()
{
n=read();
for (int i=;i<=n;i++)a[i]=read();
for (int i=;i<=n;i++)s1.push_back(a[i]);
for (int i=;i<=n;i++)s2.push_back(a[n-i+]);
while(s1[]!=)
{
spin(s1[]);
ans++;
if (ans>)
{
printf("-1\n");
return ;
}
}
printf("%d\n",ans);
}
splay代码
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstdio> #define N 300007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,ans,rt;
int a[N];
int c[N][],fa[N],siz[N],val[N];
bool rev[N]; void update(int k)
{
int l=c[k][],r=c[k][];
siz[k]=siz[l]+siz[r]+;
}
void rotate(int x,int &k)
{
int y=fa[x],z=fa[y],l,r;
if (c[y][]==x)l=;else l=;r=l^;
if (y==k) k=x;
else
{
if (c[z][]==y) c[z][]=x;
else c[z][]=x;
}
fa[x]=z,fa[y]=x,fa[c[x][r]]=y;
c[y][l]=c[x][r],c[x][r]=y;
update(y),update(x);
}
void splay(int x,int &p)
{
while(x!=p)
{
int y=fa[x],z=fa[y];
if (y!=p)
{
if (c[y][]==x^c[z][]==y) rotate(x,p);
else rotate(y,p);
}
rotate(x,p);
}
}
void pushdown(int k)
{
int l=c[k][],r=c[k][];
rev[k]^=,rev[l]^=,rev[r]^=;
swap(c[k][],c[k][]);
}
void build(int l,int r,int p)
{
if (l>r) return;
int mid=(l+r)>>;
if (mid<p) c[p][]=mid;
else c[p][]=mid;
siz[mid]=,val[mid]=a[mid],fa[mid]=p;
if (l==r) return;
build(l,mid-,mid),build(mid+,r,mid);
update(mid);
}
int find(int p,int rk)//寻找第rk的位置。
{
if (rev[p]) pushdown(p);
int l=c[p][],r=c[p][];
if (siz[l]+==rk) return p;
else if (siz[l]>=rk) return find(l,rk);
else return find(r,rk-siz[l]-);
}
void spin(int l,int r)
{
int x=find(rt,l),y=find(rt,r+);//因为加了两个虚节点，所以翻转的时候方便，1为虚节点，将2----当前位置+1这一段旋转出来。
splay(x,rt),splay(y,c[x][]);//这样根的右子树的左子树就是所求区间。
int z=c[y][];
rev[z]^=;//在这个节点上打上标记，可以想一下，现在树是什么样子的。
}
int main()
{
n=read();
for (int i=;i<=n;i++) a[i+]=read();
build(,n+,),rt=(+n+)>>;//0只是虚的点，没有用的，1和n+2是哨兵，一线段树的形式建立splay先。
while(val[find(rt,)]!=)//第二个是第一个数
{
ans++;
spin(,val[find(rt,)]);
if (ans>)
{
printf("-1\n");
return ;
}
}//操作直到第一个是1。
printf("%d\n",ans);
}
发现手写splay快，常数大但是比c++的大部分的stl还是快的，stl没有开O3，O2
是很慢的，而且可持久化平衡树更强大，就需要更大的代价。