P3165 [CQOI2014]排序机械臂

时间：2021-05-31 14:39:36

题目描述

为了把工厂中高低不等的物品按从低到高排好序，工程师发明了一种排序机械臂。它遵循一个简单的排序规则，第一次操作找到高度最低的物品的位置 P1P_1P1​ ，并把左起第一个物品至 P1P_1P1​ 间的物品 (即区间 [1,P1][1,P_1][1,P1​] 间的物品) 反序；第二次找到第二低的物品的位置 P2P_2P2​ ，并把左起第二个至 P2P_2P2​ 间的物品 (即区间 [2,P2][2,P_2][2,P2​] 间的物品) 反序……最终所有的物品都会被排好序。

P3165 [CQOI2014]排序机械臂

上图给出有六个物品的示例，第一次操作前，高度最低的物品在位置 444 ，于是把第一至第四的物品反序；第二次操作前，第二低的物品在位罝六，于是把第二至六的物品反序……

你的任务便是编写一个程序，确定一个操作序列，即每次操作前第 iii 低的物品所在位置 PiP_iPi​ ，以便机械臂工作。需要注意的是，如果有高度相同的物品，必须保证排序后它们的相对位置关系与初始时相同。

输入输出格式

输入格式：

第一行包含正整数n,表示需要排序的物品数星。

第二行包含n个空格分隔的整数PiP_iPi​,表示每个物品的高度。

输出格式：

输出一行包含n个空格分隔的整数Pi。

输入输出样例

输入样例#1： 
6

3 4 5 1 6 2
输出样例#1： 
4 6 4 5 6 6

说明

N<=100000

Pi<=10^7

Solution：

　　本题既然区间反转，那么Splay裸题。

　　首先对高度排序得到操作的顺序，再对初始位置中序遍历建树。

　　对于每次操作的原位置，将其旋到根，答案(新的位置)就是其左子树的大小，然后因为它的前趋之前的数已经位置固定，那么只要把它和后继所在的子树翻转，所以把前趋旋转到根，再把后继旋转到根的右儿子，打上懒惰标记就好了。

　　注意，每次在splay改变树的形态时下放标记，用栈存下一条链上的节点并下放，在查排名的时候也得下放标记。

代码：

/*Code by 520 -- 9.20*/

#include<bits/stdc++.h>

#define il inline

#define ll long long

#define RE register

#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)

#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)

#define son(x) (x==ch[fa[x]][1])

using namespace std;

const int N=;

int n,ans,stk[N],top;

int root,cnt,ch[N][],siz[N],lazy[N],fa[N];

struct node{

    int v,id;

    bool operator < (const node &a) const {return v==a.v?id<a.id:v<a.v;}

}a[N];

int gi(){

    int a=;char x=getchar();bool f=;

    while((x<''||x>'')&&x!='-') x=getchar();

    if(x=='-') x=getchar(),f=;

    while(x>=''&&x<='') a=(a<<)+(a<<)+(x^),x=getchar();

    return f?-a:a;

}

il void pushup(int rt){siz[rt]=siz[ch[rt][]]+siz[ch[rt][]]+;}

il void pushdown(int rt){

    if(lazy[rt]){

        lazy[ch[rt][]]^=,lazy[ch[rt][]]^=;

        swap(ch[rt][],ch[rt][]),lazy[rt]=;

    }

}

il void rotate(int x){

    int y=fa[x],z=fa[y],b=son(x),c=son(y),a=ch[x][!b];

    z?ch[z][c]=x:root=x; fa[x]=z;

    if(a) fa[a]=y; ch[y][b]=a;

    fa[y]=x,ch[x][!b]=y;

    pushup(y),pushup(x);

}

il void splay(int x,int i){

    int tp=x;top=;

    while(fa[tp]!=i) stk[++top]=tp,tp=fa[tp];

    while(top) pushdown(stk[top--]);

    while(fa[x]!=i){

        int y=fa[x],z=fa[y];

        if(z==i) rotate(x);

        else {

            if(son(x)==son(y)) rotate(y),rotate(x);

            else rotate(x),rotate(x);

        }

    }

}

int build(int l,int r,int lst){

    int rt=l+r>>;

    fa[rt]=lst,siz[rt]=;

    if(l<rt) ch[rt][]=build(l,rt-,rt);

    if(r>rt) ch[rt][]=build(rt+,r,rt);

    pushup(rt);return rt;

}

il int getrank(int x){

    int rt=root;

    while(){

        pushdown(rt);

        if(siz[ch[rt][]]>=x&&ch[rt][]) rt=ch[rt][];

        else {

            x-=siz[ch[rt][]]+;

            if(!x) return rt;

            rt=ch[rt][];

        }

    }

}

int main(){

    n=gi();

    a[]={-0x7fffffff,},a[n+]={0x7fffffff,n+};

    For(i,,n+) a[i].v=gi(),a[i].id=i;

    sort(a+,a+n+);

    root=build(,n+,);

    For(i,,n) {

        splay(a[i].id,);

        ans=siz[ch[root][]]+;

        printf("%d ",ans-);

        int pre=getrank(i-),suc=getrank(ans+);

        splay(pre,),splay(suc,pre);

        lazy[ch[ch[root][]][]]^=;

    }

    printf("%d",n);

    return ;

}

相关文章