「ARC 080E」Young Maids-线段树 + 堆

给出一个 $1 \sim n$ 的排列,$p_0, p_2, \cdots, p_{n - 1}$,每次从中选相邻两数删去,加入 $q$ 的前面,求最小字典序的 $q$。

链接

ARC 080E

题解

首先 $q_0$ 显然必须是最小的,并且它一定在 $p$ 中的偶数位置,我们直接在 $p$ 中的偶数位置找到最小的 $p_i$ 作为 $q_0$,对于 $q_1$,只能是 $p$ 中的奇数位置且在 $p_i$ 后,设其为 $p_j$。

那么 $p$ 现在最多可以被分成三段 $[0, i), [i + 1, j), [j + 1, n)$,对于 $q_2$,它一定在这三段中,并且它所在位置的奇偶性与第一个元素相同,同理 $q_3$ 也像 $q_1$ 一样找,这样我们就有了一个 $O(n ^ 2)$ 的做法。

考虑用线段树做 rmq,用堆来维护区间 $[l, r), l, \leq i < r, i \equiv l \ \ (\text{mod 2})$ 中最小的 $p_i$。

时间复杂度 $O(n \log n)$。

代码

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
/**
* Copyright (c) 2017, xehoth
* All rights reserved.
* 「ARC 080E」Young Maids 26-08-2017
* 线段树 + 堆
* @author xehoth
*/
#include <bits/stdc++.h>
namespace Task {
const int MAXN = 200000;
int M;
inline void init(const int n) {
for (M = 1; M < n + 2; M <<= 1)
;
}
struct SegmentTree {
int d[MAXN * 4];
inline void maintain(int k) { d[k] = std::min(d[k << 1], d[k << 1 | 1]); }
inline void build() {
for (register int i = M - 1; i; i--) maintain(i);
}
inline int query(int s, int t) const {
register int ret = INT_MAX;
for (s = s + M - 1, t = t + M + 1; s ^ t ^ 1; s >>= 1, t >>= 1) {
(~s & 1) ? ret = std::min(ret, d[s ^ 1]) : 0;
(t & 1) ? ret = std::min(ret, d[t ^ 1]) : 0;
}
return ret;
}
};
SegmentTree even, odd;
int a[MAXN + 1], pos[MAXN + 1];
struct Node {
int l, r, x;
Node(int l, int r, int x) : l(l), r(r), x(x) {}
inline bool operator<(const Node &b) const { return x > b.x; }
};
template <typename T>
class PriorityQueue : public std::priority_queue<T> {
private:
#define super std::priority_queue<T>
public:
inline void reserve(const int n) { super::c.reserve(n); }
#undef super
};
inline void initRmq(const int n, const int *a) {
init(n);
for (register int i = 1; i <= n; i++) {
if (i & 1) {
odd.d[M + i] = a[i], even.d[M + i] = INT_MAX;
} else {
even.d[M + i] = a[i], odd.d[M + i] = INT_MAX;
}
}
even.build(), odd.build();
}
inline void solve() {
std::ios::sync_with_stdio(false), std::cin.tie(NULL), std::cout.tie(NULL);
register int n;
std::cin >> n;
for (register int i = 1; i <= n; i++) std::cin >> a[i], pos[a[i]] = i;
initRmq(n, a);
static PriorityQueue<Node> q;
q.reserve(n * 2);
q.push(Node(1, n, odd.query(1, n)));
const SegmentTree *t[2] = {&even, &odd};
while (!q.empty()) {
Node d = q.top();
q.pop();
register int l = d.l, r = d.r;
register int p1 = pos[d.x], p2 = pos[t[~p1 & 1]->query(p1 + 1, r)];
std::cout << a[p1] << ' ' << a[p2] << ' ';
if (l < p1) q.push(Node(l, p1 - 1, t[l & 1]->query(l, p1 - 1)));
if (p1 < p2 - 1)
q.push(Node(p1 + 1, p2 - 1, t[~p1 & 1]->query(p1 + 1, p2 - 1)));
if (p2 < r) q.push(Node(p2 + 1, r, t[~p2 & 1]->query(p2 + 1, r)));
}
}
}
int main() {
Task::solve();
return 0;
}
分享到