[bzoj1552\bzoj2506][Cqoi2014]robotic sort 排序机械臂_非旋转Treap

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010 
#define mp make_pair
using namespace std;
typedef pair<int,int> par;
struct pig
{
    int val,id,fin_val;
}t[N];
int n;
inline bool cmp1(pig x,pig y)
{
    if(x.val!=y.val)return x.val<y.val;
    return x.id<y.id;
}
inline bool cmp2(pig x,pig y)
{
    return x.id<y.id;
}
struct Node
{
    int ls,rs,size,key,fa;
    bool turn;
}a[N];
int root;
inline void update(int x)
{
    int ls=a[x].ls,rs=a[x].rs;
    a[x].size=1;
    if(ls)a[x].size+=a[ls].size;
    if(rs)a[x].size+=a[rs].size;
}
inline void pushdown(int x)
{
    if(a[x].turn)
    {
        swap(a[x].ls,a[x].rs);
        if(a[x].ls)a[a[x].ls].turn^=1;
        if(a[x].rs)a[a[x].rs].turn^=1;
        a[x].turn=0;
    }
}
int merge(int x,int y)
{
    pushdown(x);pushdown(y);
    if(!x||!y)return x|y;
    if(a[x].key>a[y].key)
    {
        a[x].rs=merge(a[x].rs,y);
        a[a[x].rs].fa=x;
        update(x);
        return x;
    }
    a[y].ls=merge(x,a[y].ls);
    a[a[y].ls].fa=y;
    update(y);
    return y;
}
par split(int x,int k)
{
    pushdown(x);
    if(!k)return mp(0,x);
    int ls=a[x].ls,rs=a[x].rs;
    if(k==a[ls].size)
    {
        a[ls].fa=0;
        a[x].ls=0;update(x);
        return mp(ls,x);
    }
    if(k==a[ls].size+1)
    {
        a[rs].fa=0;
        a[x].rs=0;update(x);
        return mp(x,rs);
    }
    if(k<a[ls].size)
    {
        par t=split(ls,k);
        a[t.first].fa=0,a[t.second].fa=x;
        a[x].ls=t.second;
        update(x);
        return mp(t.first,x);
    }
    par t=split(rs,k-a[ls].size-1);
    a[t.first].fa=x,a[t.second].fa=0;
    a[x].rs=t.first;
    update(x);
    return mp(x,t.second);
}
int z[N],top;
int getrank(int x)
{
    top=0;int t=x;
    while(t)z[++top]=t,t=a[t].fa;
    while(top)pushdown(z[top--]);
    int ans=0,flag=1;
    while(x)
    {
        if(flag)ans+=a[a[x].ls].size+1;
        flag=(x==a[a[x].fa].rs);
        x=a[x].fa;
    }
    return ans;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&t[i].val),t[i].id=i;
    sort(t+1,t+n+1,cmp1);
    for(int i=1;i<=n;i++)t[i].fin_val=i;
    sort(t+1,t+n+1,cmp2);
    for(int i=1;i<=n;i++)
    {
        int pos=t[i].fin_val;
        a[pos].key=rand(),a[pos].size=1;
        root=merge(root,pos);
    }
    for(int i=1;i<=n;i++)
    {
        int rank=getrank(i);
        printf("%d",rank);
        if(n-i)putchar(' ');
        if(i==rank)continue;
        par t2=split(root,rank),t1=split(t2.first,i-1);
        a[t1.second].turn^=1;
        root=merge(merge(t1.first,t1.second),t2.second);
    }
    return 0;
}