DTOI-5 排序最大值 (Maximum Version) - 算法详解与代码实现

DTOI-5 排序最大值 (Maximum Version) - 算法详解与代码实现/n/n本题与 Minimum Version 的区别是所求最值和数据范围不同。/n/n小 L 热衷于重排数列使之规整。/n/n### 题目描述/n/n小 L 有一个长为 n 的序列 a，其中每一项 a_i 都是一个 pair (p_i, q_i)。/n/n为了让 a 看起来规整一些，他钦定 p, q 分别均为长为 n 的排列。/n/n为了对 a 的规整程度进行量化计算，他给出了一个权值函数 f(a) = ∑_{i = 1}ⁿ ([p_i > max_{j = 1}^{i - 1} p_j] + [q_i > max_{j = 1}^{i - 1} q_j])。注意 i = 1 时两个方括号都能取到值，因为我们认为 max_{j = 1}⁰ p_j = max_{j = 1}⁰ q_j = -∞。/n/n为了让 a 看起来更加规整，他决定分别以某种方式重排 a 得到 a' 使得 f(a') 最大。注意重排时必须将 a'_i = (p'_i, q'_i) 视为整体。/n/n他希望你求出 f(a')_max 的值，以及分别有多少个 a' 可以取到 f(a')_max。/n/n由于方案数可能很大，你只需要求出结果对 998244353 取模的值。/n/n### 输入格式/n/n第一行，一个整数 n；/n/n第二行，n 个整数 p₁, p₂, ..., p_n；/n/n第三行，n 个整数 q₁, q₂, ..., q_n。/n/n### 输出格式/n/n一行，两个整数，表示所求的值。/n/n### 样例 #1/n/n#### 样例输入 #1/n/n/n5/n1 5 2 4 3/n1 4 2 5 3/n/n/n#### 样例输出 #1/n/n/n9 2/n/n/n### 提示/n/n*【数据范围】/n/n$$//def//or{//operatorname{or}}//def//arrayscretch{1.5}//def//arraystretch{1.5}//begin{array}{|c|c|c|}/hline//textbf{Subtask}&n//le &//textbf{Points}//cr//hline//sf1&10&10 //operatorname{pts}//cr//hline//sf2&50&20 //operatorname{pts}//cr//hline//sf3&500&20 //operatorname{pts}//cr//hline//sf4&2//times 10^3&20 //operatorname{pts}//cr//hline//sf5&/&30 //operatorname{pts}//cr//hline//end{array}$$/n/n对于 100% 的数据，1 ≤ n ≤ 10⁴，1 ≤ p_i, q_i ≤ n，保证 p, q 均为排列**。/n/n### 算法分析/n/n本题可以使用多种算法解决，下面将逐步介绍每种算法的思路和实现：/n/n#### 算法 1：暴力枚举 (O(n³))/n/n对于每个排列 p,q，暴力计算 f(a) 并更新答案和方案数。/n/n##### 时间复杂度/n/n总时间复杂度 O(n³)。/n/n#### 算法 2：优化枚举 (O(n²log n))/n/n考虑优化枚举 p 和 q 的过程。/n/n对于每个 p_i，我们可以用一个数组 c_p 记录 p 中比 p_i 小的数的个数，那么 [p_i > max_{j = 1}^{i - 1} p_j] 就可以在 O(1) 时间内计算出来。/n/n同理，我们可以用一个数组 c_q 记录 q 中比 q_i 小的数的个数，那么 [q_i > max_{j = 1}^{i - 1} q_j] 也可以在 O(1) 时间内计算出来。/n/n这样，计算 f(a) 的时间复杂度就从 O(n) 降为 O(1)。/n/n##### 时间复杂度/n/n总时间复杂度 O(n²log n)。/n/n#### 算法 3：排序+树状数组 (O(n log n))/n/n考虑对 a 进行排序，使得 p 递增，q 递减。/n/n对于 p，我们可以用树状数组维护 [1, i - 1] 中比 p_i 小的数的个数，那么 [p_i > max_{j = 1}^{i - 1} p_j] 就可以在 O(log n) 时间内计算出来。/n/n同理，我们可以用树状数组维护 [1, i - 1] 中比 q_i 大的数的个数，那么 [q_i > max_{j = 1}^{i - 1} q_j] 也可以在 O(log n) 时间内计算出来。/n/n##### 时间复杂度/n/n总时间复杂度 O(n log n)。/n/n#### 算法 4：排序+双指针 (O(n log n))/n/n考虑对 a 进行排序，使得 p 递增，q 递减。/n/n用两个指针 l 和 r 分别指向 p 和 q，从后向前扫描。/n/n用 c_p 和 c_q 分别记录当前指针所指的数前面比它小的数的个数。/n/n如果当前 p_l > q_r，那么 [p_l > max_{j = 1}^{l - 1} p_j] 就可以计算出来，l 向前移动一格。/n/n同理，如果当前 p_l < q_r，那么 [q_r > max_{j = 1}^{r - 1} q_j] 就可以计算出来，r 向前移动一格。/n/n如果当前 p_l = q_r，那么 [p_l > max_{j = 1}^{l - 1} p_j] 和 [q_r > max_{j = 1}^{r - 1} q_j] 都可以计算出来，l 和 r 同时向前移动一格。/n/n##### 时间复杂度/n/n总时间复杂度 O(n log n)。/n/n### C++ 代码/n/n#### 算法 2/n/nc++/n#include <bits/stdc++.h>/nusing namespace std;/n/nconst int MOD = 998244353;/n/nint main() {/n int n;/n cin >> n;/n vector<int> p(n), q(n);/n for (int i = 0; i < n; i++) cin >> p[i];/n for (int i = 0; i < n; i++) cin >> q[i];/n/n long long ans = 0, cnt = 0;/n for (int i = 0; i < n; i++) {/n for (int j = 0; j < n; j++) {/n vector<int> cp(n, 0), cq(n, 0);/n for (int k = 0; k < i; k++) {/n if (p[k] < p[i]) cp[p[k]]++;/n if (q[k] < q[j]) cq[q[k]]++;/n }/n long long f = cp[p[i]] + cq[q[j]];/n if (f > ans) {/n ans = f;/n cnt = 1;/n } else if (f == ans) {/n cnt++;/n }/n }/n }/n/n cout << ans << ' ' << cnt % MOD << endl;/n return 0;/n}/n/n