题目大意
「Codeforces 1187D」Subarray Sorting
给定长度为 $n$ 的两个数列 $A, B$，问是否可以做若干次「将 $A$ 的某个区间升序排序」把 $A$ 变为 $B$。
数据范围：$n \le 3 \times 10^5$。
思路分析
发现自己最近连水题都不会做了 QAQ。
首先把「将 $A$ 的某个区间升序排序」这种操作替换成「将 $A$ 的某两个相邻的数升序排序」这种操作以方便思考。转化后的题目其实本质没有变化，因为我们可以用冒泡排序的方式实现「将一个区间排序」。
然后逐位考虑，假设现在考虑到 $A_i$，前 $i - 1$ 位已经排好了。那么我们如果要让操作过后的 $A_i$ 要和 $B_i$ 相等，就必须从 $A$ 的后面把一个等于 $B_i$ 的数调动到第 $i$ 位。我们找到数列 $A$ 从 $i$ 开始的第一个 $A_j = B_i$，考虑调动 $A_j$。不难发现这个数能被成功调动当且仅当所有 $A_k (i \le k < j)$ 都小于它自己。于是我们暴力地模拟这个过程即可得到一个 $O(n^2)$ 的算法。
可惜这并不能通过本题，考虑使用数据结构优化。我们可以直接使用平衡树维护这个过程，但我们还有更简单的方法。发现我们只需要用到一个数列没被调动过的数的前缀最大值。于是我们每次调动完一个数后，我们将它赋值为 $-1$，这样，它就不会被算进最大值中了。对于还可使用的数，我们使用线段树维护区间最大值即可。如何实现寻找 $A$ 中可使用的第一个 $A_j = B_i$ 呢？我们开 $n$ 个队列，第 $i$ 个存储 $A$ 中数值为 $i$ 的数的出现位置；每次找数时，我们只需取出队首即可。总时间复杂度 $O(n \log n)$。
代码实现
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | using namespace std; |
8 | |
9 | const int maxn = 3e5, maxm = maxn * 4; |
10 | int T, n, a[maxn + 3], b[maxn + 3], mx[maxm + 3]; |
11 | queue<int> app[maxn + 3]; |
12 | |
13 | void maintain(int x) { |
14 | mx[x] = max(mx[ls], mx[rs]); |
15 | } |
16 | |
17 | void modify(int x, int l, int r, int y, int z) { |
18 | if (l == r) { |
19 | mx[x] = z; |
20 | return; |
21 | } |
22 | if (y <= mid) { |
23 | modify(ls, l, mid, y, z); |
24 | } else { |
25 | modify(rs, mid + 1, r, y, z); |
26 | } |
27 | maintain(x); |
28 | } |
29 | |
30 | int query(int x, int l, int r, int lx, int rx) { |
31 | if (lx > rx) { |
32 | return 0; |
33 | } |
34 | if (l >= lx && r <= rx) { |
35 | return mx[x]; |
36 | } |
37 | int res = 0; |
38 | if (lx <= mid) { |
39 | res = max(res, query(ls, l, mid, lx, rx)); |
40 | } |
41 | if (rx > mid) { |
42 | res = max(res, query(rs, mid + 1, r, lx, rx)); |
43 | } |
44 | return res; |
45 | } |
46 | |
47 | int main() { |
48 | scanf("%d", &T); |
49 | while (T--) { |
50 | for (int i = 1; i <= n; i++) { |
51 | queue<int> t; |
52 | swap(t, app[i]); |
53 | } |
54 | for (int i = 1; i <= n * 4; i++) { |
55 | mx[i] = 0; |
56 | } |
57 | scanf("%d", &n); |
58 | for (int i = 1; i <= n; i++) { |
59 | scanf("%d", &a[i]); |
60 | a[i] = n - a[i] + 1; |
61 | app[a[i]].push(i); |
62 | modify(1, 1, n, i, a[i]); |
63 | } |
64 | for (int i = 1; i <= n; i++) { |
65 | scanf("%d", &b[i]); |
66 | b[i] = n - b[i] + 1; |
67 | } |
68 | bool flag = true; |
69 | for (int i = 1; i <= n; i++) { |
70 | if (app[b[i]].empty()) { |
71 | flag = false; |
72 | break; |
73 | } |
74 | int x = app[b[i]].front(); |
75 | app[b[i]].pop(); |
76 | if (query(1, 1, n, 1, x - 1) > a[x]) { |
77 | flag = false; |
78 | break; |
79 | } |
80 | modify(1, 1, n, x, 0); |
81 | } |
82 | puts(flag ? "YES" : "NO"); |
83 | } |
84 | return 0; |
85 | } |