题目重述

给定一个长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$。
一个子序列（不要求连续）被称为 “整齐子序列”，如果对于任意一个值 $v$，它在子序列中出现的次数要么是 $0$，要么恰好等于 $v$。

例如，可以包含 $1$ 个 $1$、$2$ 个 $2$、$3$ 个 $3$，但不能包含 $2$ 个 $1$ 或 $1$ 个 $2$。

求最长的整齐子序列的长度。

---

动态规划状态定义

设 $dp(i)$ 表示考虑前缀 $[a_1, a_2, \dots, a_i]$ 时，能获得的最长整齐子序列的长度。

显然，$dp$ 是非递减的：

$$dp(0) \le dp(1) \le \dots \le dp(n)$$

因为前缀 $i$ 的解一定是前缀 $i-1$ 的解的一个子集，或者可以从前缀 $i-1$ 的解继承过来（不选 $a_i$）。

---

转移方程推导

当我们计算 $dp(i)$ 时，考虑 $a_i$ 是否被选入整齐子序列：

情况 1：不选 $a_i$

此时最优解就是前缀 $i-1$ 的最优解，即：

$$dp(i) = dp(i-1)$$

情况 2：选 $a_i$

如果 $a_i$ 被选中，那么根据整齐子序列的定义，值 $a_i$ 在子序列中必须出现恰好 $a_i$ 次。
并且我们假设 $a_i$ 是子序列的最后一个元素（因为我们是从左到右递推的，可以这样考虑）。

为了最大化长度，我们希望这 $a_i$ 个 $a_i$ 在数组中 尽可能靠右 地被选取，这样前面的前缀 $[1, x-1]$ 就能容纳更多的元素（因为 $dp$ 单调递增）。

具体来说，设 $x$ 是数组 $[a_1, a_2, \dots, a_i]$ 中值 $a_i$ 的 第 $a_i$ 大的下标，即从右往左数第 $a_i$ 个 $a_i$ 的位置。
那么我们可以这样构造子序列：

• 从 $[1, x-1]$ 中取一个最优整齐子序列（长度为 $dp(x-1)$）
• 再取上 $x$ 位置开始的这 $a_i$ 个 $a_i$（即 $a_x, a_{x+1}, \dots, a_i$ 中所有等于 $a_i$ 的 $a_i$ 个元素）

这样构造出的子序列中，值 $a_i$ 恰好出现 $a_i$ 次（因为从 $x$ 到 $i$ 正好有 $a_i$ 个 $a_i$，并且 $x$ 是第 $a_i$ 个 $a_i$），并且前面的部分与这些 $a_i$ 互不干扰（因为 $x-1$ 及之前没有额外的 $a_i$ 被选入？等一下，需要小心）

更严格的分析：
如果 $x$ 是第 $a_i$ 大的 $a_i$ 的位置，那么从 $x$ 到 $i$ 恰好有 $a_i$ 个 $a_i$。
如果我们在子序列中包含这 $a_i$ 个 $a_i$，并且保证子序列中其他位置的值与它们不冲突，那么这样是合法的。
前面的部分 $[1, x-1]$ 可以独立地选出一个最优整齐子序列（长度为 $dp(x-1)$），加上这 $a_i$ 个元素，总长度为：

$$dp(x-1) + a_i$$

因此，情况 2 的候选答案为：

$$dp(x-1) + a_i$$

---

最终转移

综合两种情况：

$$dp(i) = \max \left( dp(i-1),\; dp(x-1) + a_i \right) $$

其中 $x$ 是值 $a_i$ 在 $[1, i]$ 中出现的倒数第 $a_i$ 个位置（即第 $a_i$ 大的下标）。
如果 $a_i$ 在 $[1, i]$ 中出现的次数不足 $a_i$，则情况 2 不可能发生，此时只有 $dp(i) = dp(i-1)$。

---

高效实现

我们需要在 $O(1)$ 时间内找到 $x$。

维护队列

对于每个不同的值 $v$，我们维护一个队列 $q[v]$，存储它出现的下标。
当遍历到 $a_i$ 时：

1. 将 $i$ 入队 $q[a_i]$。
2. 如果 $q[a_i]$ 的大小超过 $a_i$，则弹出队首（因为队列只保留最近的 $a_i$ 个出现位置）。
3. 如果 $q[a_i]$ 的大小恰好等于 $a_i$，则队首元素就是 $x$（即倒数第 $a_i$ 个 $a_i$ 的位置）。

于是转移可以快速完成：

$$dp(i) = \max(dp(i-1),\; dp(q[a_i].front() - 1) + a_i) $$

---

代码解析

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 10;
int T, n, a[MAXN], dp[MAXN];
deque<int> q[MAXN];

int main() {
    for (scanf("%d", &T); T--; ) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) q[i].clear();   // 清空所有队列
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1];                        // 不选 a[i] 的情况
            q[a[i]].emplace_back(i);                  // 将当前位置入队
            if (q[a[i]].size() > a[i]) 
                q[a[i]].pop_front();                  // 保持队列长度 ≤ a[i]
            if (q[a[i]].size() == a[i]) {             // 恰好有 a[i] 个 a[i] 在队列中
                int x = q[a[i]].front();              // x 是倒数第 a[i] 个 a[i] 的位置
                dp[i] = max(dp[i], dp[x - 1] + a[i]); // 更新 dp[i]
            }
        }
        printf("%d\n", dp[n]);
    }
}

---

复杂度分析

• 每个位置 $i$ 只入队一次、出队最多一次，因此所有队列操作的总复杂度为 $O(n)$。
• 每个 $dp(i)$ 的计算是 $O(1)$。
• 总时间复杂度：$O(n)$ 每个测试用例。
• 空间复杂度：$O(n)$ 用于存储队列和数组。

---

总结

这道题的关键在于：

1. 利用 $dp$ 的单调性，贪心地选择最靠右的 $a_i$ 个 $a_i$。
2. 用队列维护每个值最近的出现位置，快速找到转移所需的 $x$。
3. 状态转移方程：

$$dp(i) = \max(dp(i-1),\; dp(x-1) + a_i)$$

其中 $x$ 是值 $a_i$ 的倒数第 $a_i$ 次出现位置。