题目重述

对于数组 $c$，定义 $d_x(c)$ 为值 $x$ 在 $c$ 中任意两次出现之间的最大间隔：

$$d_x(c) = \max_{i < j,\ c_i = c_j = x} (j - i)$$

若 $x$ 出现少于两次，则 $d_x(c) = 0$。

数组 $c$ 的美丽值为：

$$\text{beauty}(c) = \sum_{x=1}^{n} d_x(c)$$

给定数组 $a$（$1 \le a_i \le n$），一个数组 $b$ 称为 nice，如果：

• $|b| = n$
• $1 \le b_i \le a_i$ 对所有 $1 \le i \le n$ 成立

求所有 nice 数组 $b$ 的最大可能美丽值。

---

解题思路

第一步：关键观察

对于任意值 $x$，设它在数组 $b$ 中第一次出现的位置为 $L_x$，最后一次出现的位置为 $R_x$（若出现至少两次）。那么：

$$d_x(b) = R_x - L_x$$

中间的所有出现不会影响这个距离。因此，我们只需要关心每个值的第一次和最后一次出现位置。

---

第二步：将距离和转化为位置贡献

将 $R_x - L_x$ 写成求和形式：

$$R_x - L_x = \sum_{k = L_x}^{R_x - 1} 1$$

这意味着，对于每个位置 $k$（$1 \le k \le n-1$），如果有值 $x$ 满足 $L_x \le k < R_x$，那么这个值 $x$ 就会对位置 $k$ 贡献 $1$。

因此，总美丽值可以写成：

$$\text{beauty} = \sum_{k=1}^{n-1} \left|\{x : L_x \le k < R_x\}\right| $$

定义 $cross(k) = |\{x : L_x \le k < R_x\}|$，则：

$$\text{beauty} = \sum_{k=1}^{n-1} cross(k)$$

---

第三步：问题转化

现在问题转化为：对于每个位置 $k$，我们希望最大化 $cross(k)$，即尽可能多的值 $x$ 满足其开始位置 $\le k$ 且结束位置 $> k$。

每个值 $x$ 的 $L_x$ 和 $R_x$ 必须满足：

• $L_x$ 是一个位置 $i$，且 $a_i \ge x$（因为可以在该位置放置 $x$）
• $R_x$ 是一个位置 $j$，且 $a_j \ge x$，并且 $j > L_x$

---

第四步：标程的核心算法

标程使用贪心算法分别计算前缀和后缀的最优值。

4.1 计算前缀能开始的不同值数量 $pre[i]$

从左到右遍历位置 $i = 1$ 到 $n$：

• 维护一个集合 $S$，初始包含所有值 $\{1, 2, \dots, n\}$
• 对于位置 $i$，在 $S$ 中找到小于等于 $a_i$ 的最大值
• 如果找到这样的值，就把它从 $S$ 中删除（表示这个值可以在位置 $i$ 开始）
• $pre[i] = n - |S|$，表示前缀 $[1, i]$ 中能开始的不同值的最大数量

贪心正确性：为了让前缀能开始尽可能多的不同值，应该优先让较小的值在较早的位置开始。较大的 $a_i$ 可以容纳较大的值，而较小的 $a_i$ 只能容纳较小的值，贪心选择小于等于 $a_i$ 的最大值可以最小化浪费。

4.2 计算后缀能结束的不同值数量 $suf[i]$

从右到左遍历位置 $i = n$ 到 $1$：

• 维护一个集合 $S$，初始包含所有值 $\{1, 2, \dots, n\}$
• 对于位置 $i$，在 $S$ 中找到小于等于 $a_i$ 的最大值
• 如果找到这样的值，就把它从 $S$ 中删除（表示这个值可以在位置 $i$ 结束）
• $suf[i] = n - |S|$，表示后缀 $[i, n]$ 中能结束的不同值的最大数量

4.3 计算答案

对于每个切分点 $k$（$1 \le k \le n-1$）：

• 前缀 $[1, k]$ 中能开始的不同值数量为 $pre[k]$
• 后缀 $[k+1, n]$ 中能结束的不同值数量为 $suf[k+1]$
• 这两部分能配对的最大数量是 $\min(pre[k], suf[k+1])$，因为这受限于开始和结束的较小者

最终答案：

$$\text{ans} = \sum_{k=1}^{n-1} \min(pre[k], suf[k+1]) $$

---

第五步：正确性证明

上界性：对于任何位置 $k$，跨越它的不同值 $x$ 必须满足 $L_x \le k$ 且 $R_x \ge k+1$。因此，跨越 $k$ 的值数量不超过前缀 $[1, k]$ 中能开始的不同值数量，也不超过后缀 $[k+1, n]$ 中能结束的不同值数量，所以不超过 $\min(pre[k], suf[k+1])$。

可达性：可以通过构造证明存在一种方案，使得对于所有 $k$ 同时达到这个上界。构造方法是将值按贪心配对，使得每个值的开始和结束位置分别取自前缀和后缀的最优位置。

贪心最优性：用 $set$ 维护未使用值，每次取小于等于 $a_i$ 的最大值，可以最大化每个前缀能开始的不同值数量。这是因为较大的 $a_i$ 可以容纳较大的值，而较小的 $a_i$ 只能容纳较小的值，贪心保证了最小化浪费。

---

算法复杂度

• 每个测试用例：
  • 两次遍历，每次 $O(n \log n)$（$set$ 操作）
  • 一次求和 $O(n)$
• 总复杂度：$O(\sum n \log n) \le O(2 \times 10^5 \log (2 \times 10^5))$，可以通过。

---

示例验证

以第一个样例 $a = [1, 2, 1, 2]$ 为例：

计算 $pre[i]$（前缀开始数）：

$i$	$a_i$	可选值	删除的值	$pre[i]$
$1$		$\{1\}$	$1$
$2$		$\{2\}$	$2$	$2$
$3$	$1$	$\{\}$	无
$4$	$2$

计算 $suf[i]$（后缀结束数）：

从右到左：

$i$	$a_i$	可选值	删除的值	$suf[i]$
$4$	$2$	$\{2\}$	$2$	$1$
$3$	$1$	$\{1\}$	$1$	$2$
$2$		$\{\}$	无
$1$

计算答案：

$$k=1: \min(pre[1], suf[2]) = \min(1, 2) = 1$$ $$k=2: \min(pre[2], suf[3]) = \min(2, 2) = 2$$ $$k=3: \min(pre[3], suf[4]) = \min(2, 1) = 1$$ $$\text{ans} = 1 + 2 + 1 = 4$$

与样例输出一致。

---

代码实现（带注释）

#include <bits/stdc++.h>
using namespace std;

const int MAXN = (int)1e6 + 7;
int n, t, ans;
int arr[MAXN], f[MAXN][2];
set<int> st;

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];

    // 计算前缀能开始的不同值数量（j=0）和后缀能结束的不同值数量（j=1）
    for (int j = 0; j < 2; j++) {
        st.clear();
        // 初始所有值都可用
        for (int i = 1; i <= n; i++) st.insert(i);
        
        // j=0: 从左到右遍历，计算前缀
        // j=1: 从右到左遍历，计算后缀
        for (int i = (j ? n : 1); (j ? i > 1 : i < n); (j ? i-- : i++)) {
            // 找到小于等于 arr[i] 的最大可用值
            auto it = st.upper_bound(arr[i]);
            if (it != st.begin()) {
                it--;
                st.erase(*it);  // 用掉这个值
            }
            f[i][j] = n - st.size();  // 已用值的数量
        }
    }
    
    // 计算答案：对每个切分点取 min 后求和
    ans = 0;
    for (int i = 1; i < n; i++) {
        ans += min(f[i][0], f[i + 1][1]);
    }
    
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> t;
    while (t--) solve();
    
    return 0;
}

---

总结

这道题的核心技巧是：

1. 将距离和转化为位置贡献：每个位置 $k$ 统计有多少个值的区间覆盖了它
2. 分别计算前缀和后缀的最优值：使用贪心算法，每次取小于等于 $a_i$ 的最大可用值
3. 取 min 后求和：每个位置的贡献受限于前缀开始数和后缀结束数的较小值

这种方法将原问题转化为了一个可以在 $O(n \log n)$ 时间内解决的问题。