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

这道题与 Maximum Version 的区别在于最值和数据范围不同，但是思路其实是相似的。

注意到 $f(a)$ 的定义中，每一项只和前面的最大值有关，因此可以考虑维护前缀的最大值。

具体地，假设已经确定了前 $i-1$ 项 $(p_1',q_1'),(p_2',q_2'),\ldots,(p_{i-1}',q_{i-1}')$ 的排列 $p'$ 和 $q'$，以及前缀的最大值 $mp_p=\max_{j=1}^{i-1}p_j$ 和 $mp_q=\max_{j=1}^{i-1}q_j$。那么第 $i$ 项 $(p_i,q_i)$ 的排序方式只和 $mp_p,mp_q$ 以及 $p_i,q_i$ 的大小关系有关。

具体地，如果 $p_i>mp_p$ 且 $q_i>mp_q$，那么 $(p_i,q_i)$ 一定可以放在最后；如果 $p_i>mp_p$ 且 $q_i\leq mp_q$，那么 $(p_i,q_i)$ 必须放在所有 $q_j>mp_q$ 的 $(p_j,q_j)$ 之后；如果 $p_i\leq mp_p$ 且 $q_i>mp_q$，那么 $(p_i,q_i)$ 必须放在所有 $p_j>mp_p$ 的 $(p_j,q_j)$ 之后；如果 $p_i\leq mp_p$ 且 $q_i\leq mp_q$，那么 $(p_i,q_i)$ 可以放在所有 $(p_j,q_j)$ 之前或之后，这两种情况都是合法的。

于是，我们可以考虑按照 $mp_p$ 和 $mp_q$ 的大小关系分成 $4$ 个区间，分别对每个区间进行排序。由于排序的复杂度为 $O(n\log n)$，所以总复杂度为 $O(n\log n)$。

考虑如何计算方案数。对于一个区间，我们可以先找到所有与 $mp_p$ 和 $mp_q$ 相等的位置，将它们固定下来，然后对于剩余的位置进行排列。注意到这个排列的过程是相互独立的，所以可以分别计算每个区间的方案数，最后相乘即可。

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

完整代码