技不如人，甘拜下风。

题目链接

题意：有一个排列$p$，每次操作会取出排列中所有$p_i = \max \lbrace p_j | 1 \le j \le i \rbrace$的所有元素，按原来的顺序移到序列的最后。问需要几次才能排好序。($n \le 250000$)

定义$q_i$为$i$的位置，即$p_{q_i} = i$。

设$T_i$为将所有$\ge i$的元素排好序的次数。容易发现可以忽视掉序列中$< i$的元素，如果进行了$T_{i + 1}$次操作后，$i$是序列中$\ge i$的第一个元素，那么$T_i = T_{i + 1}$，否则$T_i = T_{i+1} + 1$。

设$f_i$为进行$T_i - 1$次操作后，序列中$\ge i$的第一个元素(如果$T_i = 0$，$f_i$无意义)，那么有$f_i > i$。在计算$T_i$时，$T_i = T_{i+1}$当且仅当在进行了$T_{i+1} - 1$次操作后，$q_{f_{i+1}} < q_i < q_{i+1}$。

接下来证明一个结论：无论进行多少次操作，$f_{i+1}$、$i$、$i+1$这三个数的位置关系永远是旋转同构的($(a, b, c)$、$(b, c, a)$、$(c, a, b)$视为旋转同构)。

先证明一个引理：在进行操作的过程中，忽视$< i$的元素，如果$f_i$不是第一个元素，那么它不会成为某一个前缀最大值。

证明如下：假设有一个不是第一个元素的前缀最大值，设它为$x$。设$x$之前的一个元素为$y$，有$y < x$。进行若干次操作之后，如果$y$和$x$不相邻了，那么一定是在$y$之前存在一个$z$满足$y < z < x$。那么这次操作后$z$一定在$x$前一个位置。所以$x$之前一定有一个比$x$小的元素，所以$f_i \ne x$。

之后再证明结论：

对于$f_{i+1}, i, i + 1$这三个元素的位置关系，只要枚举一下所有情况，即可得证。上面的引理可以保证如果$i + 1$在$f_{i+1}$之前，那么$f_{i+1}$不会成为前缀最大值。

接下来就可以计算答案了($q_i$是还未进行操作时$i$的位置)：

如果$T_{i+1} = 0$：

  • 如果$q_i < q_{i+1}$，$T_i = 0$。
  • 否则$T_i = 1$，$f_i = i + 1$。

否则：

  • 如果$q_{f_{i+1}}$、$q_i$、$q_{i+1}$这三个数的关系和它们排序之后的关系旋转同构，那么$T_i = T_{i+1}$，$f_i = f_{i + 1}$。
  • 否则$T_i = T_{i+1} + 1$，$f_i = i + 1$。

复杂度$O(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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6;
int n, pos[maxn + 10], t[maxn + 10], f[maxn + 10];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		int x; scanf("%d", &x); pos[x] = i;
	}
	for (int i = n - 1; i >= 1; --i) {
		if (!t[i + 1]) {
			if (pos[i] < pos[i + 1]) t[i] = 0;
			else {
				t[i] = 1; f[i] = i + 1;
			}
		} else {
			int x = pos[f[i + 1]], y = pos[i], z = pos[i + 1];
			if ((x < y) + (y < z) + (z < x) == 2) {
				t[i] = t[i + 1]; f[i] = f[i + 1];
			} else {
				t[i] = t[i + 1] + 1; f[i] = i + 1;
			}
		}
	}
	printf("%d", t[1]);
}