It's Mooin' Time II

题意

给定一个长度为 $N$ 的数组。一个 moo 是形如 [m,o,o] 的长度为 3 的数组，其中 $m != o$ 。

如果能从原数组中删除一些元素，保留出 [m,o,o] 这个子序列，就称这种 moo 出现过。

求出现过多少种不同的 moo。不同只看数值序列，也就是不同的 (m,o)。

思路

先看一个最直接的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 15:20
 * update_at: 2026-07-11 15:23
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n;
int a[MAXN];
bool seen[MAXN][MAXN]; // seen[m][o] 表示 moo [m,o,o] 是否已经出现。

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 小数据暴力：直接枚举所有 i < j < k。
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            for (int k = j + 1; k <= n; k++) {
                if (a[i] != a[j] && a[j] == a[k]) {
                    seen[a[i]][a[j]] = true;
                }
            }
        }
    }

    long long ans = 0;
    for (int m = 1; m <= n; m++) {
        for (int o = 1; o <= n; o++) {
            if (seen[m][o]) ans++;
        }
    }

    cout << ans << '\n';

    return 0;
}

这个暴力枚举所有 $i<j<k$ ，如果 a[i] != a[j] 且 a[j] == a[k]，就把 (a[i], a[j]) 标记为出现。它完全符合题意，但三重枚举只能用于小数据。

考虑一个固定的后两位值 o。只要在某个位置之后还能找到两个 o，那么它左侧出现过的任意不同值 $m != o$ 都可以组成 [m,o,o]。

为了避免重复统计同一个 (m,o)，我们只在 o 的倒数第二次出现处统计。因为此时当前位置和最后一个 o 正好可以作为 moo 的后两位。

从左到右扫描，维护：

cnt_right[x]：当前位置及右侧还剩多少个 x。
cnt_left[x]：当前位置左侧已经出现过多少个 x。
distinct_left：左侧不同数字的数量。

当扫到 x，如果 cnt_right[x] == 2，说明当前位置是 x 的倒数第二次出现。此时左侧所有不同值都能作为 m，但如果左侧已经出现过 x，要减去 1，因为要求 $m != o$ 。

然后再把当前位置从右侧移动到左侧。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 15:20
 * update_at: 2026-07-11 15:23
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;

int n;
int a[MAXN];
int cnt_left[MAXN];   // 已经扫过的前缀中，每个值出现了多少次。
int cnt_right[MAXN];  // 当前及右侧后缀中，每个值还剩多少次。

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        cnt_right[a[i]]++;
    }

    long long ans = 0;
    int distinct_left = 0; // 左侧出现过的不同数的个数。

    for (int i = 1; i <= n; i++) {
        int x = a[i];

        // 如果从当前位置到右侧刚好还剩两个 x，那么 i 可以作为 moo 中第一个 o。
        if (cnt_right[x] == 2) {
            ans += distinct_left;
            if (cnt_left[x] > 0) {
                ans--; // m 不能等于 o，排除左侧出现过的 x。
            }
        }

        cnt_right[x]--;
        if (cnt_left[x] == 0) {
            distinct_left++;
        }
        cnt_left[x]++;
    }

    cout << ans << '\n';

    return 0;
}

复杂度

统计一次、扫描一次。

时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

总结

本题的去重关键是：每个 o 只在它的倒数第二次出现处贡献答案。

这样所有能作为第一位的 m 都在左侧，只需要维护左侧不同值数量，并排除 $m=o$ 。

目录

题意

思路

代码

复杂度

总结