SP2059 CERC07S - Robotic Sort 题解

· · 题解

题目要求我们对一个序列进行一系列反转操作，使得这个序列最终有序。

对于第 i 次旋转，我们都需要找到第 i 小的数，记其位置为 p_i，然后反转 [i,p_i] 这段区间。

说到区间反转，我们就可以想到使用 Splay。
这样就可以借鉴文艺平衡树的思路了。

我们每一次查询一个权值所对应的节点。找到我们需要反转的区间之后，将其左端点的前驱旋至根，然后将其右端点的后继旋至左端点前驱的下面，这样就拎出来了整个区间了。
然后直接打反转标记即可。

但是我们还有一个问题。就是题目给出的序列是无序的，我们还需要自己排序。
同时题目还要求我们做到稳定的排序。也就是两个物品如果高度相等，排序后它们的相对位置关系需要与初始时相同。
那么我们拿一个结构体记录一下每一个物品的高度和一开始的位置，然后按照权值排序。

然后我们再建立一颗 Splay，像上面说的那样维护、反转区间就可以了。

同时题目要求输出第 i 低的物品在操作之前的位置，我们就先将其代表的节点旋到根，其当前在序列内的位置就是其左子树的大小加上 1。
这里我向序列中加入了两个哨兵节点，这样会使左子树的大小增加 1，直接输出左子树的大小就可以了。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 100010;
const int INF = 1e8;
int n, m;
struct Node
{
    int s[2], fa;
    int v, sz;
    int flag;
};
Node tr[N];
int rt;
void maintain(int p)
{
    tr[p].sz = tr[tr[p].s[0]].sz + tr[tr[p].s[1]].sz + 1;
}
void pushdown(int p)
{
    if(tr[p].flag)
    {
        if(tr[p].s[0])tr[tr[p].s[0]].flag ^= 1;
        if(tr[p].s[1])tr[tr[p].s[1]].flag ^= 1;
        swap(tr[p].s[0], tr[p].s[1]);
        tr[p].flag = 0;
    }
}
void rotate(int x)
{
    int y = tr[x].fa, z = tr[y].fa;
    int k = (tr[y].s[1] == x) ? 1 : 0;
    tr[z].s[tr[z].s[1] == y] = x, tr[x].fa = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].fa = y;
    tr[x].s[k ^ 1] = y, tr[y].fa = x;
    maintain(y); maintain(x);
}
void splay(int x, int k)
{
    while(tr[x].fa != k)
    {
        int y = tr[x].fa, z = tr[y].fa;
        pushdown(z), pushdown(y), pushdown(x);
        if(z != k)
        {
            if((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    if(!k)rt = x;
}
void build(int &p, int l, int r)
{
    if(l > r)return;
    int mid = (l + r) >> 1;
    p = mid;
    if(l == r)
    {
        tr[p].sz = 1;
        return;
    }
    if(l < mid)
    {
        build(tr[p].s[0], l, mid - 1);
        tr[tr[p].s[0]].fa = p;
    }
    if(r > mid)
    {
        build(tr[p].s[1], mid + 1, r);
        tr[tr[p].s[1]].fa = p;
    }
    maintain(p);
}
int get_k(int k)
{
    int p = rt;
    while(true)
    {
        pushdown(p);
        if(tr[tr[p].s[0]].sz >= k && tr[p].s[0])p = tr[p].s[0];
        else
        {
            k -= tr[tr[p].s[0]].sz + 1;
            if(k == 0)return p;
            else p = tr[p].s[1];
        }
    }
}
struct TBS
{
    int x, pos;
    bool operator < (const TBS &a)const
    {
        return (x == a.x) ? pos < a.pos : x < a.x;
    }
}p[N];
int main()
{
    scanf("%d", &n);
    p[1] = { -INF,1 }, p[n + 2] = { INF,n + 2 };
    for(int i = 2; i <= n + 1; i++)
    {
        scanf("%d", &p[i].x);
        p[i].pos = i;
    }
    sort(p + 2, p + 2 + n);
    build(rt, 1, n + 2);
    for(int i = 2; i <= n; i++)
    {
        splay(p[i].pos, 0);
        int ans = tr[tr[rt].s[0]].sz;
        printf("%d ", ans);
        int L = get_k(i - 1);
        int R = get_k(ans + 2);
        splay(L, 0); splay(R, L);
        tr[tr[R].s[0]].flag ^= 1;
    }
    printf("%d\n", n);
    return 0;
}

四 倍 经 验