Eva

Description

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

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

6
3 4 5 1 6 2

4 6 4 5 6 6

/**************************************************************

    Problem: 3506

    User: ictsing

    Language: C++

    Result: Accepted

    Time:3468 ms

    Memory:5200 kb

****************************************************************/

 

//1552: [Cerc2007]robotic sort

/*

感觉是比较有收获的题目

首先读入所有的价值（即标号）

排序之后把rankk记录出来

然后记录rankki在splay中的结点标号tot

这个只能记录并且永远不会变，因为splay中价值无序，并没有办法查询，除非遍历整棵树

然后把排序后的物品扫一遍，

顺着splay旋转到根节点，

左子数即当前位置

然后不能像往常一样a[0]=-inf,a[mt]=inf

因为rankk数组会炸掉，rankk[1]=0,rankk[n+2]=n+1;

*/

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

const int mt = 100000+5;

int rankk[mt],retot[mt],ch[mt][2],f[mt],sz[mt],cnt[mt],rev[mt];

int rt,tot;

struct ha

{

    int val,id;

}a[mt];

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

       ch=getchar();

       if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

       num=num*10+ch-'0';

       ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

bool cmp(ha a,ha b)

{

    return (a.val<b.val)||(a.val==b.val&&a.id<b.id);//吐血，，，sort不稳定排序后面半句话一定要加

}

int get(int x)

{

    return ch[f[x]][1]==x;

}

void update(int x)

{

    if(x)

    {

        sz[x]=cnt[x];

        if(ch[x][0]) sz[x]+=sz[ch[x][0]];

        if(ch[x][1]) sz[x]+=sz[ch[x][1]];

    }

}

void pushdown(int x)

{

    if(x)

    {

        if(rev[x])

        {

            swap(ch[x][0],ch[x][1]);

            if(ch[x][0]) rev[ch[x][0]]^=1;

            if(ch[x][1]) rev[ch[x][1]]^=1;

            rev[x]=0;

        }

    }

}

void rotate(int x)

{

    pushdown(f[x]),pushdown(x);

    int old=f[x],fold=f[old],which=get(x);

    ch[old][which]=ch[x][which^1],f[ch[x][which^1]]=old;

    ch[x][which^1]=old,f[old]=x;

    f[x]=fold;

    if(fold)

        ch[fold][ch[fold][1]==old]=x;

    update(old),update(x);

}

void splay(int x,int rrt)

{

    for(int fa;(fa=f[x])!=rrt;rotate(x))

        if(f[fa]!=rrt)

            rotate((get(x)==get(fa))?fa:x);

    if(rrt==0) rt=x;

}

int build(int l,int r,int fa)

{

    if(l>r)

        return 0;

    int now=++tot;

    int mid=(l+r)>>1;

    f[now]=fa;

    retot[rankk[mid]]=now;

    sz[now]=cnt[now]=1;rev[now]=0;

    int ls=build(l,mid-1,now);

    int rs=build(mid+1,r,now);

    ch[now][0]=ls,ch[now][1]=rs;

    update(now);

    return now;

}

int askk(int x)

{

    int now=rt;

    while(true)

    {

        pushdown(now);

        if(ch[now][0]&&x<=sz[ch[now][0]])

            now=ch[now][0];

        else

        {

            int tmp=(ch[now][0]?sz[ch[now][0]]:0)+cnt[now];

            if(x<=tmp) return now;

            x-=tmp,now=ch[now][1];

        }

    }

}

int main()

{

    int n=read();

    for(int i=1;i<=n;i++)

        a[i].val=read(),a[i].id=i;

    sort(a+1,a+n+1,cmp);

    rankk[1]=0,rankk[n+2]=n+1;

    for(int i=1;i<=n;i++)

        rankk[a[i].id+1]=i;

    rt=build(1,n+2,0);

    for(int i=1;i<=n;i++)

    {

        int ovo=retot[i];

        splay(ovo,0);

        if(i!=n) printf("%d ",sz[ch[rt][0]]);//+1-1);

        else printf("%d\n",sz[ch[rt][0]]);//+1-1);

        //i-1 ans+1

        int x=i,y=sz[ch[rt][0]]+2;

        if(x>y) swap(x,y);

        int aa=askk(x);

        int bb=askk(y);

        splay(aa,0);

        splay(bb,aa);

        rev[ch[ch[rt][1]][0]]^=1;

    }

    return 0;

}