SP2059 CERC07S - Robotic Sort 题解

题意：

你要为一个机器人编写软件，来对一些物品进行排序。

这个机器人每次能够选择任意数量的连续物品将其旋转。它的操作遵循一个简单的原则：

第一次操作时，找到高度最低的物品的位置 \(P_1\) ，然后把区间 \([1,P_1]\) 翻转；

第二次操作时，找到剩余物品中高度最低的物品的位置 \(P_2\) ，然后把区间 \([2,P_2]\) 翻转；

以此类推，第 \(i\) 次操作时，找到剩余物品中高度最低的物品的位置\(P_i\)，然后把区间 \([i,P_i]\) 翻转。

注意，如果有高度相同的物品，则应保持其排序后的相对顺序与初始的相对顺序相同。

~~精美插图~~：

输入格式：

输入包含多个场景。每个场景由两行描述。第一行包含一个整数 \(N\)，表示样本数量，\(1 \le N \le 10^5\)。第二行列出了恰好 \(N\) 个用空格分隔的正整数，这些整数指定了每个样本的高度及其初始顺序。

最后一个场景以包含零的一行结束。（~~scenario 在这里翻译成场景好像还真没啥问题~~）

输出格式：

对于每个场景，输出一行，恰好包含 \(N\) 个整数 \(P_1,P_2,\cdots P_N\)，用空格分隔。每个 \(P_i\) 必须是一个整数 \((1 \le P_i \le N)\)，表示第 \(i\) 个样本在第 \(i\) 次反转操作之前的位置。

请注意，如果一个样本已经在其正确的位置 \(P_i\)，你仍然需要输出数字 \(P_i\)，表示“\(P_i\) 和 \(P_i\) 之间的区间”（单个样本）应被反转。

考虑对序列排序，按物品的值为第一关键字，初始编号为第二关键字

这样序列就相当于有序了，初始编号就是文艺平衡树里的权值，当前编号就是编号（废话）。

题目要求输出 \(P_i\) 在当前操作前的位置，我们可以把它对应的节点 splay 到根

这样在当前序列中的位置就是左子树的大小（本来要加 \(1\) 的，但是 splay 里有哨兵节点）

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int n;
namespace Splay
{
    int tot, rt; 
    #define ls(at) t[at].ch[0]
    #define rs(at) t[at].ch[1]
    struct cxy { int v, id; } a[N];
    struct node { int ch[2], num, fa, cnt, sz, tag; } t[N];
    int New(int x, int f)
    {
        t[++tot] = {0, 0, x, f, 1, 1, 0};
        if(f) t[f].ch[x > t[f].num] = tot;
        return tot;
    }
    void push_up(int at) {
        t[at].sz = t[ls(at)].sz + t[rs(at)].sz + t[at].cnt;
    }
    void push_down(int at)
    {
        if(t[at].tag)
        {
            if(ls(at)) t[ls(at)].tag ^= 1;
            if(rs(at)) t[rs(at)].tag ^= 1;
            t[at].tag = 0; swap(ls(at), rs(at));
        }
    }
    void rotate(int x)
    {
        int y = t[x].fa, z = t[y].fa, k = rs(y) == x;
        t[z].ch[rs(z) == y] = x; t[x].fa = z;
        t[y].ch[k] = t[x].ch[k ^ 1]; t[t[x].ch[k ^ 1]].fa = y;
        t[x].ch[k ^ 1] = y; t[y].fa = x;
        push_up(y); push_up(x);
    }
    void splay(int x, int goal)
    {
        while(t[x].fa != goal)
        {
            int y = t[x].fa, z = t[y].fa;
            push_down(z); push_down(y); push_down(x);
            if(z != goal) ((rs(y) == x) ^ (rs(z) == y)) ? rotate(x) : rotate(y);
            rotate(x);
        }
        if(!goal) rt = x;
    }
    void insert(int x)
    {
        int at = rt, f = 0;
        while(at && x != t[at].num) {
            f = at; at = t[at].ch[x > t[at].num];
        }
        if(at) ++t[at].cnt; else at = New(x, f);
        splay(at, 0);
    }
    int kth(int x)
    {
        int at = rt;
        while(1)
        {
            push_down(at); int p = ls(at);
            if(x > t[p].sz + t[at].cnt)
            {
                x -= t[p].sz + t[at].cnt;
                at = t[at].ch[1];
            }else
            {
                if(x <= t[p].sz) at = p;
                else return t[at].num;
            }
        }
    }
}using namespace Splay;
void solve()
{
    a[1] = {-INF, 1}; a[n + 2] = {INF, n + 2};
    for(int i = 2; i <= n + 1; i++) { cin >> a[i].v, a[i].id = i; }
    sort(a + 2, a + 1 + n + 1, [](cxy x, cxy y){ 
        return x.v == y.v ? x.id < y.id : x.v < y.v;
    });
    for(int i = 1; i <= n + 2; i++) insert(i);
    for(int i = 2; i <= n; i++)
    {
        splay(a[i].id, 0);
        int ans = t[ls(rt)].sz; cout << ans << ' ';
        int l = kth(i - 1), r = kth(ans + 2);
        splay(l, 0); splay(r, l); t[ls(r)].tag ^= 1;
    }
    cout << n << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    while(cin >> n && n) { tot = rt = 0; solve(); }
    return 0;
}