# 「DTOI-5」进行一个排的重 Maximum Version## 题目背景本题与 Minimum Version 的区别是所求最值和数据范围不同。小 L 热衷于重排数列使之规整。## 题目描述小 L 有一个长为 $n$ 的序列 $a$其中每一项 $a_i$ 都是一个 pair $p_i q_i$。为了让 $a$ 看起来规整一些他钦定 $p q$ 分别均为长为 $n$ 的排列。为了对 $a$

算法1

(暴力枚举) $O(n^3)$

对于每个排列 $p,q$，暴力计算 $f(a)$ 并更新答案和方案数。

时间复杂度

总时间复杂度 $O(n^3)$。

算法2

(优化枚举) $O(n^2\log n)$

考虑优化枚举 $p$ 和 $q$ 的过程。

对于每个 $p_i$，我们可以用一个数组 $c_p$ 记录 $p$ 中比 $p_i$ 小的数的个数，那么 $[p_i > \max_{j = 1}^{i - 1} p_j]$ 就可以在 $O(1)$ 时间内计算出来。

同理，我们可以用一个数组 $c_q$ 记录 $q$ 中比 $q_i$ 小的数的个数，那么 $[q_i > \max_{j = 1}^{i - 1} q_j]$ 也可以在 $O(1)$ 时间内计算出来。

这样，计算 $f(a)$ 的时间复杂度就从 $O(n)$ 降为 $O(1)$。

时间复杂度

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

算法3

(排序+树状数组) $O(n\log n)$

考虑对 $a$ 进行排序，使得 $p$ 递增，$q$ 递减。

对于 $p$，我们可以用树状数组维护 $[1, i - 1]$ 中比 $p_i$ 小的数的个数，那么 $[p_i > \max_{j = 1}^{i - 1} p_j]$ 就可以在 $O(\log n)$ 时间内计算出来。

同理，我们可以用树状数组维护 $[1, i - 1]$ 中比 $q_i$ 大的数的个数，那么 $[q_i > \max_{j = 1}^{i - 1} q_j]$ 也可以在 $O(\log n)$ 时间内计算出来。

时间复杂度

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

算法4

(排序+双指针) $O(n\log n)$

考虑对 $a$ 进行排序，使得 $p$ 递增，$q$ 递减。

用两个指针 $l$ 和 $r$ 分别指向 $p$ 和 $q$，从后向前扫描。

用 $c_p$ 和 $c_q$ 分别记录当前指针所指的数前面比它小的数的个数。

如果当前 $p_l > q_r$，那么 $[p_l > \max_{j = 1}^{l - 1} p_j]$ 就可以计算出来，$l$ 向前移动一格。

同理，如果当前 $p_l < q_r$，那么 $[q_r > \max_{j = 1}^{r - 1} q_j]$ 就可以计算出来，$r$ 向前移动一格。

如果当前 $p_l = q_r$，那么 $[p_l > \max_{j = 1}^{l - 1} p_j]$ 和 $[q_r > \max_{j = 1}^{r - 1} q_j]$ 都可以计算出来，$l$ 和 $r$ 同时向前移动一格。

时间复杂度

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

C++ 代码

算法