形式化题目

给定长度为 $n$ 的序列 $a_1, a_2, \ldots, a_n$，取值都在 $1$ 到 $m$ 之间，且每个取值至少出现一次。

一个“桌面”是一串两两不同的点数，记作 $P$。向桌面处理一个点数 $k$ 的规则是：

1. 若 $k$ 不在 $P$ 中，把 $k$ 接到 $P$ 的右端，即 $P \leftarrow P \cdot k$；
2. 若 $k$ 在 $P$ 中且位置为 $q$，先删掉 $P$ 从第 $q$ 个到末尾的全部元素，再接上 $k$，即 $P \leftarrow P_{1..q-1} \cdot k$。

第 $i$ 局游戏从空桌面开始，依次处理 $a_i, a_{i+1}, \ldots, a_n$，记结束时桌面上的点数集合为 $T_i$。

要求对每个 $v \in [1, m]$ 求出

即有多少局游戏结束时桌面上留有点数为 $v$ 的牌。题面把这一串点数叫作“桌面上的牌”，下文沿用。

暴力解法

思路

最直接的做法是照题面模拟：对每个起点 $i$，维护桌面序列 table 和“点数 $v$ 在桌面上的位置”pos[v]，一路处理到第 $n$ 张牌，最后把桌面上剩下的点数都计入答案。

代码

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/**
 * 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-10-31 18:55
 * update_at: 2026-10-31 19:03
 */
// brute.cpp：照题面直接模拟每一局，桌上用数组存点数顺序，pos[v] 记录 v 在桌上的位置。
// 每局 O(n)，总 O(n^2)，只适用于小数据。
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 5;
int n, m;
int a[maxn];
int ans[maxn];

int table[maxn];   // 桌面上从左到右的点数
int pos[maxn];     // pos[v]：点数 v 在 table 中的下标，-1 表示不在桌上

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

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

    for (int i = 1; i <= n; ++i) {
        for (int v = 1; v <= m; ++v) pos[v] = -1;
        int top = 0;                       // 桌上的牌数
        for (int j = i; j <= n; ++j) {
            int k = a[j];
            if (pos[k] != -1) {            // 桌面上有点数 k 的牌，收走它和它右边的牌
                int at = pos[k];           // 先记下位置，清空时 pos[k] 会被改成 -1
                for (int t = at; t < top; ++t) pos[table[t]] = -1;
                top = at;
            }
            table[top] = k;
            pos[k] = top;
            ++top;
        }
        for (int t = 0; t < top; ++t) ++ans[table[t]];
    }

    for (int v = 1; v <= m; ++v) {
        cout << ans[v] << (v == m ? '\n' : ' ');
    }
    return 0;
}

复杂度

单局最多处理 $n$ 张牌，每张牌的收牌操作虽然可能腾掉很多元素，但每个元素最多被收走一次，所以单局是 $O(n)$。加上 $n$ 个起点，总时间 $O(n^2)$。$n \leqslant 5000$ 的测试点可以过，$n = 5 \times 10^5$ 时需要 $2.5 \times 10^{11}$ 次操作。

瓶颈

瓶颈是“每一局都从头模拟一遍”。但第 $i$ 局与第 $i+1$ 局的差别只有开头多了一张 $a_i$，逐局重算等于把大量的相同后缀反复处理。

要利用这个相似性，得先看清“多出来的那张牌会怎样影响后续”。关键在于：第 $i$ 局打出的第一张牌始终待在桌面最左端，直到它再次出现。

正解

关键观察

设第 $i$ 局打出的第一张牌点数为 $x = a_i$。它一开始就在桌面最左端。

如果 $x$ 在 $i$ 之后的位置 $j$ 再次出现：从 $i$ 到 $j-1$ 之间打出的点数都不等于 $x$，而收牌只会从“被打出的那个点数”及其右侧开始，所以最左端这张 $x$ 一轮都没被收走。到位置 $j$ 打出 $x$ 时，被收走的正是整张桌面，桌面只剩刚打出的这张 $x$。

这和第 $j$ 局的情况一模一样：第 $j$ 局第一张打的也是 $x$，打完也同样只剩一张 $x$。两局从此面对完全相同的后续牌，因此 $T_i = T_j$。

如果 $i$ 是 $x$ 的最后一次出现：这张 $x$ 永远不会被收走，永久占住桌面最左端。它右侧的部分从此再也不会受影响，其变化过程和第 $i+1$ 局（从空桌面开始）逐张对应，因此

并且 $a_i$ 排在桌面最左端。

把这两种情况合起来。记 $p_v$ 为点数 $v$ 在整个序列中最后一次出现的位置。先看 $a_i$ 多次出现的情形：第 $i$ 局的桌面与“$a_i$ 下一次出现的位置”那一局的桌面相同，而那一局的首牌还是同一个点数，于是可以一路向后连等，直到走到 $a_i$ 的最后一次出现位置 $p_{a_i}$，得到 $T_i = T_{p_{a_i}}$。而 $p_{a_i}$ 满足第二种情况，有 $T_{p_{a_i}} = \{a_i\} \cup T_{p_{a_i}+1}$，两个式子首尾一接就得到统一形式。

记 $nxt[i] = p_{a_i} + 1$（可能等于 $n+1$，表示结束），再规定 $T_{n+1} = \varnothing$，就有

右边集合的下标严格大于 $i$，递推不会绕圈。同时 $a_i$ 不会同时出现在 $T_{nxt[i]}$ 里：桌面上的点数只能来自本局处理过的那些牌，也就是 $a_{nxt[i]}, \ldots, a_n$；而 $nxt[i] = p_{a_i}+1$ 已经越过了 $a_i$ 的全部出现位置，右侧不会再出现点数 $a_i$。因此链上同一个点数最多被记一次，把链长当成桌面大小不会重复计数。

思路

把递推展开，第 $i$ 局的桌面就是一条从 $i$ 出发的链：

链上每个位置贡献自己的点数 $a_{\text{位置}}$，走到 $n+1$ 结束。

以样例 #1 的 $a = (1, 2, 1, 3)$ 为例，$p_1 = 3$、$p_2 = 2$、$p_3 = 4$，于是 $nxt = (4, 3, 4, 5)$。四条链是：

1
2
3
4第 1 局： (位置1:点数1) ──→ (位置4:点数3) ──→ 结束
第 2 局： (位置2:点数2) ──→ (位置3:点数1) ──→ (位置4:点数3) ──→ 结束
第 3 局：                    (位置3:点数1) ──→ (位置4:点数3) ──→ 结束
第 4 局：                                        (位置4:点数3) ──→ 结束

四局结束时的桌面分别是 $1\,3$、$2\,1\,3$、$1\,3$、$3$，与题面给出的结果一致。

于是问题变成：一条链上的每个位置，要为多少个起点服务。设 $cnt[i]$ 表示有多少局游戏的链经过位置 $i$。位置 $i$ 一定在自己的链上（第 $i$ 局），此外每条经过某个 $u$ 且 $nxt[u] = i$ 的链也会经过它，所以

$nxt[i] > i$，所以按 $i$ 从小到大扫一遍，把 $cnt[i]$ 加到 $cnt[nxt[i]]$ 上，就能在 $O(n)$ 内算完所有 $cnt$。最后把 $cnt[i]$ 累加到答案 $c_{a_i}$ 上：位置 $i$ 贡献的点数是 $a_i$，它被 $cnt[i]$ 局游戏的桌面包含。

按点数汇总：点数 1 出现在位置 1 和 3，贡献 $1 + 2 = 3$；点数 2 只在位置 2，贡献 1；点数 3 在位置 4，贡献 4。输出 3 1 4，与样例一致。

代码

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/**
 * 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-10-31 18:55
 * update_at: 2026-10-31 19:10
 */
// main.cpp：把每一局结束时留在桌上的点集写成一条「跳转链」：
// T[i] = { a[i] } + T[last[a[i]] + 1]，即 a[i] 这张牌最终一定留在最左端起始终不动，
// 而它右侧的局面与「最后一次出现 a[i] 之后的那一局」完全相同。
// 于是只要统计每个位置被多少条链经过，按点数累加即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 5e5 + 5;
int n, m;
int a[maxn];
int last[300005];   // last[v]：点数 v 在序列中最后一次出现的位置
ll cnt[maxn];       // cnt[i]：有多少局游戏的链经过位置 i
ll ans[300005];     // ans[v]：桌面上留有点数 v 的局数

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

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        last[a[i]] = i;         // 从左到右扫，最后一次赋值就是最后一次出现
    }

    // 每个位置自己先算一次；再把它的游戏数推给链上的下一个位置
    // 下一个位置是 last[a[i]] + 1，一定比 i 大，所以从小到大扫就能一次算完
    for (int i = 1; i <= n; ++i) cnt[i] = 1;
    cnt[n + 1] = 0;
    for (int i = 1; i <= n; ++i) {
        cnt[last[a[i]] + 1] += cnt[i];
    }

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

    for (int v = 1; v <= m; ++v) {
        cout << ans[v] << (v == m ? '\n' : ' ');
    }
    return 0;
}

复杂度

• 时间：求最后一次出现位置一次扫描，$cnt$ 递推一次扫描，汇总答案一次扫描，总 $O(n + m)$。
• 空间：序列、最后一次出现位置与 $cnt$ 数组，$O(n + m)$。

子任务覆盖分析

正解 $O(n+m)$ 直接覆盖全部测试点。暴力 $O(n^2)$ 仅覆盖前 12 个测试点（$n\le 5000$）。下表列出各测试点组的约束与覆盖情况：

正解对所有约束（含特殊性质 A、B）均采用同一套跳转链 + $cnt$ 递推，没有针对特定性质的中间层算法。特殊性质 A、B 仅影响评测机分组，不改变算法的适用范围。

总结

整道题的关键是看清“第一张牌的去向”，它决定了局面能不能被复用：

• 第一张牌在第一张之后再次出现时，它一被再次打出就带走整张桌面，于是这一局的后半段与“那张牌再次出现的位置”开局完全重合；
• 第一张牌不再出现时，它永久占住最左端，右侧的变化与“下一张牌开局”逐张对应。

两种情况都指向同一条递推 $T_i = \{a_i\} \cup T_{nxt[i]}$，把 $n$ 次模拟压缩成一张跳转图。剩下的就是在这张图上做一次“经过次数”的计数：图的每条边都从小下标指向大下标，所以从小到大推一遍就够。

一个容易写错的地方是链上会不会重复统计同一个点数。答案是不会：递推里一旦出现同一点数的再次出现，走的就是 $nxt[i] = p_{a_i}+1$ 这条跳过整段的分支，$a_i$ 不会再被记录一次。样例 #2 里点数 1 出现在位置 2 和位置 10，但第 2 局的桌面只有一张 1，可以直接验证这一点。

相关 rbook 文章

做这题用到的知识点在 rbook 算法书 上有专门章节：