Skip to content

「CERC2007」机械排序

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

题面

题目描述

SORT 公司是一个专门为人们提供排序服务的公司,该公司的宗旨是:“顺序是最美丽的”。他们的工作是通过一系列移动,将某些物品按顺序摆好。他们的工作规定只能使用如下方法排序:

先找到编号最小的物品的位置 P1P_1,将区间 [1,P1][1, P_1] 反转,再找到编号第二小的物品的位置 P2P_2,将区间 [2,P2][2, P_2] 反转……

上图是有 66 个物品的例子,编号最小的一个是在第 44 个位置。因此,最开始把前面 44 个物品反转,第二小的物品在最后一个位置,所以下一个操作是把 262 \sim 6 的物品反转,第三步操作是把 343 \sim 4 的物品进行反转……

在数据中可能存在有相同的编号,如果有多个相同的编号,则按输入的原始次序操作。

输入格式

输入共两行,第一行为一个整数 NNNN 表示物品的个数(1N1000001 \leq N \leq 100000)。

第二行为 NN 个用空格隔开的正整数,表示 NN 个物品最初排列的编号。

输出格式

输出共一行,NN 个用空格隔开的正整数 P1,P2,P3,,PnP_1, P_2, P_3, \dots, P_n1PiN1 \leq P_i \leq N),PiP_i 表示第 ii 次操作前第 ii 小的物品所在的位置。

注意:如果第 ii 次操作前,第 ii 小的物品己经在正确的位置 PiP_i 上,我们将区间 [Pi,Pi][P_i, P_i] 反转(单个物品)。

输入输出样例

样例输入 #1

6
3 4 5 1 6 2

样例输出 #1

4 6 4 5 6 6

思路

前置知识:文艺平衡树

考虑按照排名处理,每次找到最小值的排名 kk,然后翻转区间 [1,k][1, k],再删去这个最小值。对于每次操作 k+i1k + i - 1 即为答案。

代码

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <limits>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e5 + 5;

struct node {
    node *lchild, *rchild;
    size_t size;
    unsigned key;
    int value, min;
    bool reversed;

    node()
        : lchild(nullptr),
          rchild(nullptr),
          size(0),
          key(rand()),
          value(0),
          min(std::numeric_limits<int>::max()),
          reversed(false) {}

    node(int _value)
        : lchild(nullptr),
          rchild(nullptr),
          size(1),
          key(rand()),
          value(_value),
          min(_value),
          reversed(false) {}

    ~node() {
        if (lchild != nullptr) delete lchild;
        if (rchild != nullptr) delete rchild;
    }

    inline size_t lsize() {
        return lchild == nullptr ? 0 : lchild->size;
    }

    inline size_t rsize() {
        return rchild == nullptr ? 0 : rchild->size;
    }

    inline void pushup() {
        size = lsize() + 1 + rsize();
        min = value;

        if (lchild != nullptr) {
            min = std::min(min, lchild->min);
        }

        if (rchild != nullptr) {
            min = std::min(min, rchild->min);
        }
    }

    inline void pushdown() {
        if (reversed) {
            std::swap(lchild, rchild);
            if (lchild != nullptr) lchild->reversed = !lchild->reversed;
            if (rchild != nullptr) rchild->reversed = !rchild->reversed;
            reversed = false;
        }
    }
};

int n, b[N];
std::pair<int, int> a[N];
node *root;

std::pair<node *, node *> split(node *u, int k) {
    if (u == nullptr) return std::make_pair(nullptr, nullptr);

    u->pushdown();

    if (k <= u->lsize()) {
        auto o = split(u->lchild, k);

        u->lchild = o.second;
        u->pushup();
        o.second = u;

        return o;
    }

    auto o = split(u->rchild, k - u->lsize() - 1);

    u->rchild = o.first;
    u->pushup();
    o.first = u;

    return o;
}

node *merge(node *x, node *y) {
    if (x == nullptr) return y;
    if (y == nullptr) return x;

    if (x->key < y->key) {
        x->pushdown();
        x->rchild = merge(x->rchild, y);
        x->pushup();

        return x;
    }

    y->pushdown();
    y->lchild = merge(x, y->lchild);
    y->pushup();

    return y;
}

void reverse(int k) {
    auto x = split(root, k);
    auto y = split(x.first, k - 1);
    if (y.first != nullptr) y.first->reversed = !y.first->reversed;
    delete y.second;
    root = merge(y.first, x.second);
}

int find(node *p) {
    int k = 1;

    while (p != nullptr) {
        p->pushdown();

        if (p->lchild != nullptr && p->min == p->lchild->min) {
            p = p->lchild;
        } else if (p->rchild != nullptr && p->min == p->rchild->min) {
            k += p->lsize() + 1;
            p = p->rchild;
        } else {
            return k + p->lsize();
        }
    }

    return -1;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i].first;

        a[i].second = i;
    }

    std::sort(a + 1, a + 1 + n);

    for (int i = 1; i <= n; i++) {
        b[a[i].second] = i;
    }

    for (int i = 1; i <= n; i++) {
        root = merge(root, new node(b[i]));
    }

    for (int i = 1; i <= n; i++) {
        int k = find(root);

        reverse(k);

        cout << k + i - 1 << ' ';
    }

    cout << endl;

    // Cleanup
    delete root;

    return 0;
}