BZOJ1552&3506[Cqoi2014]排序机械臂

#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n;
int cnt;
int root;
int x,y,z;
int v[100010];
int s[100010];
int r[100010];
int mn[100010];
int ls[100010];
int rs[100010];
int size[100010];
struct miku
{
    int val;
    int num;
    int rak;
}a[100010];
bool cmp1(miku a,miku b)
{
    if(a.val!=b.val)
    {
        return a.val<b.val;
    }
    return a.num<b.num;
}
bool cmp2(miku a,miku b)
{
    return a.num<b.num;
}
int build(int val)
{
    int rt=++cnt;
    r[rt]=rand();
    v[rt]=val;
    mn[rt]=val;
    size[rt]=1;
    return rt;
}
void rotate(int rt)
{
    swap(ls[rt],rs[rt]);
    s[rt]^=1;
}
void pushup(int rt)
{
    size[rt]=size[ls[rt]]+size[rs[rt]]+1;
    mn[rt]=v[rt];
    if(ls[rt])
    {
        mn[rt]=min(mn[rt],mn[ls[rt]]);
    }
    if(rs[rt])
    {
        mn[rt]=min(mn[rt],mn[rs[rt]]);
    }
}
void pushdown(int rt)
{
    if(s[rt])
    {
        if(ls[rt])
        {
            rotate(ls[rt]);
        }
        if(rs[rt])
        {
            rotate(rs[rt]);
        }
        s[rt]^=1;
    }
}
int merge(int x,int y)
{
    if(!x||!y)
    {
        return x+y;
    }
    pushdown(x);
    pushdown(y);
    if(r[x]<r[y])
    {
        rs[x]=merge(rs[x],y);
        pushup(x);
        return x;
    }
    else
    {
        ls[y]=merge(x,ls[y]);
        pushup(y);
        return y;
    }
}
void split(int rt,int k,int &x,int &y)
{
    if(!rt)
    {
        x=y=0;
        return ;
    }
    pushdown(rt);
    if(size[ls[rt]]<k)
    {
        x=rt;
        split(rs[rt],k-size[ls[rt]]-1,rs[x],y);
    }
    else
    {
        y=rt;
        split(ls[rt],k,x,ls[y]);
    }
    pushup(rt);
}
int rank(int rt)
{
    pushdown(rt);
    int res=v[rt];
    if(ls[rt])
    {
        res=min(res,mn[ls[rt]]);
    }
    if(rs[rt])
    {
        res=min(res,mn[rs[rt]]);
    }
    if(res==mn[ls[rt]])
    {
        return rank(ls[rt]);
    }
    else if(res==v[rt])
    {
        return size[ls[rt]]+1;
    }
    else
    {
        return size[ls[rt]]+1+rank(rs[rt]);
    }
}
int main()
{
    srand(20020419);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].val);
        a[i].num=i;
    }   
    sort(a+1,a+1+n,cmp1);
    for(int i=1;i<=n;i++)
    {
        a[i].rak=i;
    }
    sort(a+1,a+1+n,cmp2);
    for(int i=1;i<=n;i++)
    {
        root=merge(root,build(a[i].rak));
    }
    for(int i=1;i<=n;i++)
    {  
        int ans=rank(root);
        printf("%d",i-1+ans);
        if(i!=n)
        {
            printf(" ");
        }
        split(root,ans-1,x,y);
        split(y,1,y,z);
        rotate(x);
        root=merge(x,z);
    }
}