传送门
时间限制: 2 s
空间限制: 256000 KB
题目等级 : 大师 Master
题目描述 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
新技能get√，一道伸展树竟被STL如此水过，STL块状链表(正解在下面)
#include<ext/rope>
using namespace __gnu_cxx;
rope<int>s1,s2,t1,t2;#include<cstdio>
#include<ext/rope>
#include<iostream>
using namespace std;
using namespace __gnu_cxx;
#define N 300005
rope<int>s1,s2,t1,t2;
int a[N];int n,ans;
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;
}
void rot(int s){
t1=s1.substr(0,s);
t2=s2.substr(n-s,s);
s1=t2+s1.substr(s,n-s);
s2=s2.substr(0,n-s)+t1;
}
int main(){
n=in();
for(int i=1;i<=n;i++) a[i]=in();
for(int i=1;i<=n;i++) s1.push_back(a[i]);
for(int i=n;i>=1;i--) s2.push_back(a[i]);
while(s1[0]!=1){
rot(s1[0]);ans++;
if(ans>100000){printf("%d\n",-1);return 0;}
}
printf("%d\n",ans);
return 0;
}老老实实的打SplayTree
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<iostream>
using namespace std;
struct Node{
Node *ch[2];
int r,v,s;int b;
void pushdown(){if(b){b=0;swap(ch[0],ch[1]);ch[0]->b^=1;ch[1]->b^=1;}}
Node(int v,Node *nl):v(v){r=rand();b=0;ch[0]=ch[1]=nl;s=1;}
void maintain(){s=1;s+=ch[0]->s;s+=ch[1]->s;}
}*root,*null;
void rotate(Node* &o,int d){
Node *k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;
o->maintain();k->maintain();o=k;
}
void insert(Node* &o,int x){
if(o==null){o=new Node(x,null);return;}
insert(o->ch[1],x);
if(o->ch[1]->r>o->r) rotate(o,0);
else o->maintain();
}
int cmprk(Node* o,int k){
if(o->ch[0]->s+1==k) return -1;
if(o->ch[0]->s>=k) return 0;else return 1;
}
void splay(Node* &o,int k){
if(o==null) return;
o->pushdown();
int d=cmprk(o,k);
if(d==1) k-=o->ch[0]->s+1;
if(d!=-1&&o->ch[d]!=null){
Node *p=o->ch[d];p->pushdown();
int d2=cmprk(p,k);
if(d2!=-1&&p->ch[d2]!=null){
int k2=(d2==0?k:k-p->ch[0]->s-1);
splay(p->ch[d2],k2);
if(d==d2) rotate(o,d^1);else rotate(o->ch[d],d);
}
rotate(o,d^1);
}
}
Node *merge(Node *left,Node *right){//合并
splay(left,left->s);left->ch[1]=right;
left->maintain();return left;
}
void split(Node *o,int k,Node* &left,Node* &right){//分裂 前K小在left中其余在right中
splay(o,k);left=o;right=o->ch[1];
o->ch[1]=null;left->maintain();
}
int findfirst(Node* o){
if(o->ch[0]==null&&o->ch[1]==null) return o->v;
int k=(o->b?findfirst(o->ch[1]):findfirst(o->ch[0]));
return k==0?o->v:k;
}
void init(){
null=new Node(0,0);null->r=INT_MAX;null->s=null->v=0;
null->ch[0]=null->ch[1]=null;root=null;
}
void print(Node *o){
if(o==null) return;
o->pushdown();
print(o->ch[0]);
printf("%d ",o->v);
print(o->ch[1]);
}
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;
}
int n,m,x,ans;Node *ll,*rr;
int main(){
n=in();init();
for(int i=1;i<=n;i++){
x=in();insert(root,x);
}
while(1){
x=findfirst(root);if(x==1) break;
split(root,x,ll,rr);
ll->b^=1;
root=merge(ll,rr);ans++;
if(ans>100000){printf("%d\n",-1);return 0;}
}
printf("%d\n",ans);
return 0;
}