bzoj3506【CQOI2014】排序机械臂 bzoj1552【CERC2007】robotic sort

1552: [Cerc2007]robotic sort

Time Limit: 5 Sec   Memory Limit: 64 MB
Submit: 714   Solved: 293
[ Submit][ Status][ Discuss]

Description

Input

输入共两行，第一行为一个整数N，N表示物品的个数，1<=N<=100000。第二行为N个用空格隔开的正整数，表示N个物品最初排列的编号。

Output

输出共一行，N个用空格隔开的正整数P1,P2,P3…Pn，Pi表示第i次操作前第i小的物品所在的位置。 注意：如果第i次操作前，第i小的物品己经在正确的位置Pi上，我们将区间[Pi,Pi]反转(单个物品)。

Sample Input

6
3 4 5 1 6 2

Sample Output

4 6 4 5 6 6

HINT

Source

HNOI2009集训Day6

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 100010
#define inf 1000000000
#define TOP c[c[root][1]][0]
using namespace std;
int n,root,tot;
int c[maxn][2],fa[maxn],v[maxn],mn[maxn],pos[maxn],sz[maxn],rev[maxn],ans[maxn],s[maxn];
struct data{int v,pos;}a[maxn];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline bool cmp1(data x,data y)
{
return (x.v==y.v)?x.pos<y.pos:x.v<y.v;
}
inline bool cmp2(data x,data y)
{
return x.pos<y.pos;
}
inline void pushup(int x)
{
int l=c[x][0],r=c[x][1];
mn[x]=v[x];pos[x]=x;
if (mn[l]<mn[x]) mn[x]=mn[l],pos[x]=pos[l];
if (mn[r]<mn[x]) mn[x]=mn[r],pos[x]=pos[r];
sz[x]=sz[l]+sz[r]+1;
}
inline void pushdown(int x)
{
if (!rev[x]) return;
int l=c[x][0],r=c[x][1];
rev[x]^=1;rev[l]^=1;rev[r]^=1;
swap(c[x][0],c[x][1]);
}
inline void rotate(int x,int &k)
{
int y=fa[x],z=fa[y],l=(c[y][0]==x)?0:1,r=l^1;
if (y==k) k=x;
else{if (c[z][0]==y) c[z][0]=x;else c[z][1]=x;}
fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
c[y][l]=c[x][r];c[x][r]=y;
pushup(y);pushup(x);
}
inline void splay(int x,int &k)
{
tot=0;s[++tot]=x;
for(int i=x;fa[i];i=fa[i]) s[++tot]=fa[i];
D(i,tot,1) pushdown(s[i]);
while (x!=k)
{
int y=fa[x],z=fa[y];
if (y!=k)
{
if ((c[y][0]==x)^(c[z][0]==y)) rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
inline int find(int x,int rnk)
{
pushdown(x);
int l=c[x][0],r=c[x][1];
if (sz[l]+1==rnk) return x;
else if (sz[l]>=rnk) return find(l,rnk);
else return find(r,rnk-sz[l]-1);
}
inline void split(int l,int r)
{
int x=find(root,l),y=find(root,r+2);
splay(x,root);splay(y,c[x][1]);
}
inline int query(int l,int r)
{
split(l,r);
return pos[TOP];
}
inline void rever(int l,int r)
{
split(l,r);
rev[TOP]^=1;
}
inline void build(int l,int r,int f)
{
if (l==r)
{
fa[l]=f;sz[l]=1;
mn[l]=v[l]=a[l].v;pos[l]=l;
if (l<f) c[f][0]=l;else c[f][1]=l;
return;
}
int mid=(l+r)>>1;
if (l<mid) build(l,mid-1,mid);
if (r>mid) build(mid+1,r,mid);
fa[mid]=f;v[mid]=a[mid].v;pushup(mid);
if (f&&mid<f) c[f][0]=mid;else c[f][1]=mid;
}
int main()
{
n=read();
a[1].v=a[n+2].v=inf;mn[0]=inf;
F(i,2,n+1) a[i].v=read(),a[i].pos=i;
sort(a+2,a+n+2,cmp1);
F(i,2,n+1) a[i].v=i-1;
sort(a+2,a+n+2,cmp2);
build(1,n+2,0);
root=(n+3)>>1;
F(i,1,n)
{
int x=query(i,n);
splay(x,root);
ans[i]=sz[c[x][0]];
rever(i,ans[i]);
}
F(i,1,n-1) printf("%d ",ans[i]);
printf("%d\n",ans[n]);
return 0;
}