P3165 [CQOI2014]排序机械臂

题目描述

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

样例说明

上图给出有六个物品的示例，第一次操作前，高度最低的物品在位置

你的任务便是编写一个程序，确定一个操作序列，即每次操作前第 $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=100005;
int n,ans,stk[N],top;
int root,cnt,ch[N][2],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=0;char x=getchar();bool f=0;
    while((x<'0'||x>'9')&&x!='-') x=getchar();
    if(x=='-') x=getchar(),f=1;
    while(x>='0'&&x<='9') a=(a<<3)+(a<<1)+(x^48),x=getchar();
    return f?-a:a;
}

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

il void pushdown(int rt){
    if(lazy[rt]){
        lazy[ch[rt][0]]^=1,lazy[ch[rt][1]]^=1;
        swap(ch[rt][0],ch[rt][1]),lazy[rt]=0;
    }
}

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=0;
    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>>1;
    fa[rt]=lst,siz[rt]=1;
    if(l<rt) ch[rt][0]=build(l,rt-1,rt);
    if(r>rt) ch[rt][1]=build(rt+1,r,rt);
    pushup(rt);return rt;
}

il int getrank(int x){
    int rt=root;
    while(1){
        pushdown(rt);
        if(siz[ch[rt][0]]>=x&&ch[rt][0]) rt=ch[rt][0];
        else {
            x-=siz[ch[rt][0]]+1;
            if(!x) return rt;
            rt=ch[rt][1];
        }
    }
}

int main(){
    n=gi();
    a[1]={-0x7fffffff,1},a[n+2]={0x7fffffff,n+2};
    For(i,2,n+1) a[i].v=gi(),a[i].id=i;
    sort(a+1,a+n+3);
    root=build(1,n+2,0);
    For(i,2,n) {
        splay(a[i].id,0);
        ans=siz[ch[root][0]]+1;
        printf("%d ",ans-1);
        int pre=getrank(i-1),suc=getrank(ans+1);
        splay(pre,0),splay(suc,pre);
        lazy[ch[ch[root][1]][0]]^=1;
    }
    printf("%d",n);
    return 0;
}