UVA1402 Robotic Sort 题解

Description

Luogu传送门

Solution

题目要求我们找到第 \(i\) 的数，其实就维护一下剩下的数中最小值在哪里即可。

我们考虑使用 \(fhq-treap\)。

说一下具体实现过程：

• 找到剩下的点中的最小值（其实就是根）。
• 输出答案，删去它，合并它的两个儿子。
• 维护区间翻转标记并下传。

然后就没了。。甚至连 split 都不需要（

并且维护的这个最小值正好满足小根堆的性质，为了方便，我们可以拿输入的数代替 rand 的值。

（但是会被卡）

我们考虑优化建树，使用建笛卡尔树的思想来建树。

关于笛卡尔树，戳这里。

我们把权值小于当前权值的点挂到当前点的左子树上，再把当前点挂到第一个大于它的点的右子树上，即可构建出一棵相对平衡的平衡树（事实上跑的飞快）。

这个过程就用单调栈维护一下即可。

（这样一来反而不如普通的 \(fhq-treap\) 好写了 QwQ）

还有无关紧要的一点，题目中可能会输入相同的数，如有相同先输出最靠左的，所以稍微处理一下即可，具体见代码。

Code

#include <bits/stdc++.h>
#define ll long long
#define ls(x) t[x].l
#define rs(x) t[x].r

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e5 + 10;
int n;
struct fhq_treap{
    int siz, val, l, r;
    ll wei;
    bool rev;
}t[N];
int rt, tot;

inline void pushup(int x){
    t[x].siz = t[ls(x)].siz + t[rs(x)].siz + 1;
}

inline void pushdown(int x){
    if(t[x].rev){
        swap(ls(x), rs(x));
        if(ls(x)) t[ls(x)].rev ^= 1;
        if(rs(x)) t[rs(x)].rev ^= 1;
        t[x].rev = 0;
    }
}

inline int merge(int x, int y){
    if(!x || !y) return x | y;
    if(t[x].wei <= t[y].wei){
        pushdown(x);
        rs(x) = merge(rs(x), y);
        return pushup(x), x;
    }else{
        pushdown(y);
        ls(y) = merge(x, ls(y));
        return pushup(y), y;
    }
}

int stk[N], top;

inline void build(int x){
    while(top && t[x].wei < t[stk[top]].wei) ls(x) = stk[top--], pushup(ls(x));
    if(top) rs(stk[top]) = x;
    stk[++top] = x;
}

inline void update(int x){
    int l = ls(x), r = rs(x);
    ls(x) = rs(x) = 0;
    t[l].rev ^= 1;
    rt = merge(l, r);
}

signed main(){
    while(1){
        n = read();
        if(!n) break;
        for(int i = 1; i <= n; ++i){
            t[i].wei = 1ll * read() * n + i, t[i].val = i, t[i].siz = 1;
            build(i);
        }
        while(top) pushup(rt = stk[top--]);
        for(int i = 1; i < n; ++i){
            pushdown(rt);
            write(t[ls(rt)].siz + i), putchar(' ');
            update(rt);
        }
        pushdown(rt);
        write(t[ls(rt)].siz + n), puts("");
    }
    return 0;
}

\[\_EOF\_ \]