P4402 [Cerc2007]robotic sort 机械排序

· · 题解

这是一道比较裸的平衡树模板题，这是一篇可能对细（keng）节（dian）解释比较详尽的屑题解。

思路与 文艺平衡树 相似，我们需要先增加两个哨兵节点，然后每次执行区间翻转操作时，就对区间左端点的前驱和右端点的后继进行 Splay 并把不断交换他们子节点的左右子树。而对于求解答案，我们要求的是这个节点的排名（即它在当前序列中的位置），我们可以将该节点提到根，然后统计它的左子树的大小 size（这个 size 没有算上这个节点本身，但算上了哨兵节点，所有两个影响抵消）。具体实现时，我们可以记录每个权值在平衡树中对应的节点编号记为 pos[i]，然后每次翻转时找到当前节点 pos[i] 的后继，而在我们进行这一步操作前，将要操作的值前面的数已经是有序的了，所有它的前驱便是 pos[i-1]。

注意：

  1. 我们不太能直接以编号作为平衡树的权值进行操作，这样虽然仍能实现区间翻转，但查一个数在序列中的位置会较为麻烦。
  2. 区间翻转需要提到根上的点时左端点的前驱和右端点的后继，而不是左端点和右端点（本蒟蒻就是因为这里一直不知道哪错了）。
  3. 给定数组的值可能会有相等而我们需要按输入的原始次序操作，所以我们可以将原序列重新按离散的方式重新赋值。

下面是丑陋的代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,val[300005],tag[300005],ch[300005][2],tot,rt,fa[300005],si[300005],p[300005];//p记录权值在平衡树中对应的点的编号，tag作为懒标记记录是否需要交换左右子树
struct object{
    int val,num;
}ob[300005];
inline int read(){
    int x=0,f=1;
    char ch;
    do{
        ch=getchar();
        if(ch=='-'){
            f=-1;
        }
    }while(!(ch>='0'&&ch<='9'));
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
struct Splay{
    void push_up(int cur){
        si[cur]=si[ch[cur][1]]+si[ch[cur][0]]+1;
    }
    int get(int x){
        return x==ch[fa[x]][1];
    }
    int build(int l,int r,int f){
        if(l>r){
            return 0;
        }
        int mid=(l+r)>>1;
        int now=++tot;
        fa[now]=f;
        val[now]=ob[mid].val;
        p[ob[mid].val]=now;
        ch[now][0]=build(l,mid-1,now);
        ch[now][1]=build(mid+1,r,now);
        push_up(now);
        return now;
    }
    void push_down(int cur){
        if(tag[cur]){
            tag[cur]=0;
            swap(ch[cur][0],ch[cur][1]);
            tag[ch[cur][0]]^=1;
            tag[ch[cur][1]]^=1;
        }
    }
    int nex(){//找到后继
        push_down(rt);
        int x=ch[rt][1];
        while(1){
            push_down(x);
            if(!ch[x][0]){
                break;
            }
            x=ch[x][0];
        }
        return x;
    }
    void rotate(int x){
        int y=fa[x];
        int z=fa[y];
        push_down(y);
        push_down(x);
        int chk=get(x);
        ch[y][chk]=ch[x][chk^1];
        if(ch[x][chk^1]){
            fa[ch[x][chk^1]]=y;
        }
        fa[y]=x;
        ch[x][chk^1]=y;
        fa[x]=z;
        if(z){
            ch[z][y==ch[z][1]]=x;
        }
        push_up(y);
        push_up(x);
    }
    void splay(int x,int y){
        for(int f;(f=fa[x])!=y;rotate(x)){
            if(fa[f]==y){
                continue;
            }
            if(get(x)==get(f)){
                rotate(f);
            }else{
                rotate(x);
            }
        }
        if(y==0){
            rt=x;
        }
    }
    void reverse(int l,int r){
        splay(l,0);
        splay(r,l);
        tag[ch[r][0]]^=1;
    }
}tree;//Splay模板
bool cmp(object a,object b){
    if(a.val<b.val){
        return 1;
    }else{
        if(a.val==b.val){
            return a.num<b.num;
        }
    }
    return 0;
}
bool cmp2(object a,object b){
    return a.num<b.num;
}
signed main(){
    n=read();
    for(int i=1;i<=n;++i){
        ob[i+1].val=read();
        ob[i+1].num=i+1;
    }
    ob[1].val=0;
    ob[n+2].val=n+1;
    sort(ob+2,ob+n+2,cmp);
    for(int i=2;i<=n+1;i++){
        //离散
        ob[i].val=i-1;
    }
    sort(ob+2,ob+2+n,cmp2);
    rt=tree.build(1,n+2,0);//以类似线段树的方式建数
    for(int i=1;i<=n;++i){
        int x=p[i];//找到该权值对应的点的位置
        tree.splay(x,0);
        printf("%lld ",si[ch[x][0]]);
        x=tree.nex();//该权值的后继
        int y=p[i-1];//该权值的前驱
        tree.reverse(y,x);//区间翻转
    }
    return 0;
}