Skip to content

「CERC2007」机械排序

题解约 1.1 千字
# 2014 # 数据结构 # CERC # 2007 # CQOI # 平衡树 # Treap
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

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

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

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

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

#输入格式

输入共两行，第一行为一个整数 NN，NN 表示物品的个数（1≤N≤1000001 \leq N \leq 100000）。

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

#输出格式

输出共一行，NN 个用空格隔开的正整数 P1,P2,P3,…,PnP_1, P_2, P_3, \dots, P_n（1≤Pi≤N1 \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+i−1k + i - 1 即为答案。

#代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#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;
}