1552: [Cerc2007]robotic sort
Description
Input
输入共两行，第一行为一个整数N，N表示物品的个数，1<=N<=100000。第二行为N个用空格隔开的正整数，表示N个物品最初排列的编号。
Output
输出共一行，N个用空格隔开的正整数P1,P2,P3…Pn，（1 < = Pi < = N），Pi表示第i次操作前第i小的物品所在的位置。 注意：如果第i次操作前，第i小的物品己经在正确的位置Pi上，我们将区间[Pi,Pi]反转(单个物品)。
Sample Input
6
3 4 5 1 6 2
3 4 5 1 6 2
Sample Output
4 6 4 5 6 6
Splay
#include<cstdio>
#include<algorithm>
#define MaxN 100010
using namespace std;
int N,tot,root;
struct xx{
int key,x,s;
}A[MaxN];
struct point{
int key,fa,d,x,rev,mi,minn,sum;
int son[2];
point (){
sum=rev=son[0]=son[1]=0;
}
}P[MaxN];
int cmp(const xx &a,const xx &b){
return a.key<b.key || a.key==b.key && a.x<b.x;
}
int cmp_x(const xx &a,const xx &b){
return a.x<b.x;
}
void Down(int k){
if (!P[k].rev) return;
swap(P[k].son[0],P[k].son[1]);
P[P[k].son[0]].d=0;
P[P[k].son[1]].d=1;
P[P[k].son[0]].rev^=1;
P[P[k].son[1]].rev^=1;
P[k].rev=0;
}
void Up(int k){
P[k].mi=P[k].key; P[k].minn=k;
int l=P[k].son[0],r=P[k].son[1];
P[k].sum=1+P[l].sum+P[r].sum;
if (l&&P[l].mi<P[k].mi){
P[k].mi=P[l].mi;
P[k].minn=P[l].minn;
}
if (r&&P[r].mi<P[k].mi){
P[k].mi=P[r].mi;
P[k].minn=P[r].minn;
}
}
void Turn(int x){
int y=P[x].fa; int dx=P[x].d;
int z=P[y].fa; int dy=P[y].d;
P[x].fa=z; P[x].d=dy;
if (z) P[z].son[dy]=x;
dy=1-dx; z=P[x].son[dy];
P[z].fa=y; P[z].d=dx; P[y].son[dx]=z;
P[y].fa=x; P[y].d=dy; P[x].son[dy]=y;
Up(y); Up(x);
}
void Splay(int x,int fa){
for (;P[x].fa!=fa;){
Down(P[P[x].fa].fa); Down(P[x].fa); Down(x);
if (P[P[x].fa].fa!=fa){
if (P[x].d==P[P[x].fa].d) Turn(P[x].fa);
else Turn(x);
}
if (P[x].fa==fa) break;
Turn(x);
}
if (!fa) root=x;
}
void Insert(int x,int key){
int u=root;
int fa=0;
int d=2;
++tot;
for (;;){
if (!u){
P[tot].x=x;
P[tot].key=key;
P[tot].d=d;
P[tot].fa=fa;
P[tot].mi=key;
P[tot].minn=tot;
P[tot].sum=1;
if (fa)
P[fa].son[d]=tot;
break;
}
if (key<P[u].mi){
P[u].mi=key;
P[u].minn=tot;
}
++P[u].sum;
if (x<P[u].x)d=0;
else d=1;
fa=u;
u=P[u].son[d];
}
Splay(tot,0);
}
int find(int k){
int u=root;
int s=0;
for (;;){
Down(u);
if (P[P[u].son[0]].sum+s+1==k) return u;
if (P[P[u].son[0]].sum+s+1>k)
u=P[u].son[0];
else {
s+=P[P[u].son[0]].sum+1;
u=P[u].son[1];
}
}
}
int Min(int l,int r){
int u1=find(l);
int u2=find(r+2);
Splay(u1,0);
Splay(u2,u1);
return P[P[u2].son[0]].minn;
}
int Sum(int u){
Splay(u,0);
return P[P[u].son[0]].sum+1;
}
void Rev(int l,int r){
int u1=find(l);
int u2=find(Sum(r)+1);
Splay(u1,0);
Splay(u2,u1);
P[P[u2].son[0]].rev^=1;
}
int main(){
scanf("%d",&N);
for (int i=1;i<=N;++i){
scanf("%d",&A[i].key);
A[i].x=i;
}
sort(A+1,A+N+1,cmp);
for (int i=1;i<=N;++i)
A[i].s=i;
sort(A+1,A+N+1,cmp_x);
Insert(0,0);
for (int i=1;i<=N;++i)
Insert(i,A[i].s);
Insert(N+1,0);
for (int i=1;i<=N;++i){
int k=Min(i,N);
printf("%d",Sum(k)-1);
if (i^N) printf(" ");
else printf("\n");
Rev(i,k);
}
}
评论 (0)
