I. 可微波子序列 详细题解

问题重述

给定长度为 $N$ 的数组 $A$，值域 $[1, M]$。对于每一对 $(x, y)$（$1 \le x < y \le M$），定义 $f(x, y)$ 为最长的可微波子序列的长度，其中子序列只包含 $x$ 和 $y$，且相邻元素不同（即交替出现）。求所有 $f(x, y)$ 的和。

关键观察

1. 值是否出现：若一个值在 $A$ 中至少出现一次，则称其为出现值，否则为未出现值。设出现值的总数为 $c$。

   • 若 $x, y$ 均未出现，则 $f(x, y) = 0$。
   • 若恰有一个出现，则 $f(x, y) = 1$（因为可以取单个出现的那个值）。这样的对共有 $c \times (M - c)$ 个。
   • 若两者均出现，则需要进一步计算。

2. 两个值均出现的情况：对于固定的 $x, y$，考虑原数组中所有 $x$ 和 $y$ 按原顺序构成的序列。该序列中相邻不同的对数记为 $p(x, y)$，则最长交替子序列的长度为 $p(x, y) + 1$。因为每对相邻的不同值可以保留，而连续相同的值只能保留一个。因此：

   $$f(x, y) = 1 + p(x, y)$$

   其中 $p(x, y)$ 等于满足以下条件的相邻位置对 $(i, j)$（$i < j$）的个数：

   • $A_i, A_j \in \{x, y\}$ 且 $A_i \neq A_j$；
   • 区间 $(i, j)$ 内没有其他 $x$ 或 $y$（即 $x$ 和 $y$ 在过滤后的序列中相邻）。

3. 总和的分解：

   $$\text{答案} = \underbrace{c(M-c)}_{\text{恰一个出现}} \;+\; \underbrace{\binom{c}{2}}_{\text{两个出现的基础1}} \;+\; \underbrace{\sum_{x<y} p(x, y)}_{\text{所有相邻不同对的总数}} $$

   因此问题转化为计算所有不同的出现值对 $(x, y)$ 的相邻不同对总数。

计算相邻不同对总数

对于每个位置 $i$，设 $v = A_i$，并设 $\text{last}[v]$ 为 $v$ 上一次出现的位置（若未出现过则为 $0$）。考虑所有之前出现过的值 $u \neq v$，且 $u$ 的最后一次出现位置为 $\text{last}[u]$。若 $\text{last}[u] \ge \text{last}[v]$，则 $(\text{last}[u], i)$ 构成一个合法的相邻不同对（因为区间 $(\text{last}[u], i)$ 内没有 $u$ 和 $v$）。这是因为 $u$ 的最近一次出现就是 $\text{last}[u]$，而 $v$ 的最近一次出现 $\text{last}[v] \le \text{last}[u]$，所以中间不会出现 $v$。

因此，对于当前 $i$，贡献的合法对数量为：

$$\text{其他出现值的个数} - \#\{\text{last}[u] < \text{last}[v]\} $$

其中“其他出现值”指的是已经出现过且不等于 $v$ 的值。

维护两个变量：

• $cur$：当前已经出现过的不同值的个数（即 $\text{last}[u] > 0$ 的 $u$ 的数量）。
• 一个树状数组（Fenwick Tree），记录每个最后出现位置上的标记（值为 $1$），支持单点更新和前缀和查询。

遍历数组 $i = 1 \to N$：

• $v = A[i]$
• $pre = \text{last}[v]$（若 $v$ 未出现过则为 $0$）
• $other = cur - (pre \neq 0 ? 1 : 0)$ （其他出现值的个数）
• $less = \begin{cases} \text{BIT.query}(pre-1) & \text{if } pre > 0 \\ 0 & \text{otherwise} \end{cases}$
• $add = other - less$，累加到总答案 $total$ 中。
• 然后更新：
  • 若 $pre \neq 0$，则 $\text{BIT.add}(pre, -1)$（移除旧位置）
  • $\text{BIT.add}(i, 1)$（添加新位置）
  • $\text{last}[v] = i$
  • 若 $pre = 0$，则 $cur \leftarrow cur + 1$（新值出现）

遍历结束后，$total$ 即为所有相邻不同对的总数 $\sum_{x<y} p(x, y)$。

最终答案

设 $c = cur$（最终出现值的总数），则

$$\text{答案} = total + c(M-c) + \frac{c(c-1)}{2}$$

时间复杂度 $O(N \log N)$，空间 $O(N + M)$，满足 $N, M \le 300000$。

参考代码

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

// 树状数组
struct BIT {
    int n;
    vector<int> bit;
    BIT(int sz) : n(sz), bit(sz + 2, 0) {}
    void add(int idx, int delta) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += delta;
    }
    int sum(int idx) {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    vector<int> last(M + 1, 0);
    BIT bit(N + 5);
    ll total_pairs = 0;
    int cur = 0; // 当前出现过的不同值的个数
    for (int i = 1; i <= N; ++i) {
        int v = A[i-1];
        int pre = last[v];
        int other = cur - (pre != 0 ? 1 : 0);
        int less = (pre > 0 ? bit.sum(pre - 1) : 0);
        total_pairs += other - less;
        // 更新
        if (pre != 0) bit.add(pre, -1);
        bit.add(i, 1);
        last[v] = i;
        if (pre == 0) ++cur;
    }
    ll c = cur;
    ll ans = total_pairs + c * (M - c) + c * (c - 1) / 2;
    cout << ans << '\n';
    return 0;
}