一、题目重现

椰程信奥 - T4 纸牌游戏

题目描述

小 Z 有一叠 n 张特制纸牌，从上到下的点数依次为 a_1, a_2, …, a_n。每张牌的点数是 1 到 m 之间的整数，且每种点数都至少出现一次。

他要进行 n 局相互独立的游戏。每局开始前把所有牌按原顺序放回、清空桌面；第 i 局跳过前 i−1 张，依次打出第 i 张到第 n 张，点数依次是 ai, a{i+1}, …, a_n。

桌面上的牌始终从左到右排成一行。打出一张点数为 k 的牌时：

• 若桌面上没有点数为 k 的牌，就把它放在最右端；
• 否则，收走桌面上点数为 k 的那张牌及其右侧的所有牌，再把新打出的这张 k 放在最右端。被收走的牌本局不再使用。

由规则可知，任意时刻桌面上同一种点数的牌至多只有一张。最后一张牌打出后本局结束。

例：桌上是 1 4 2，打出 3 后变成 1 4 2 3；再打出 4，桌上原来的 4 及其右侧的 4 2 3 被收走，新 4 放到最右，桌上变成 1 4。

求：对每个 i = 1, 2, …, m，在全部 n 局游戏中，有多少局结束时桌面上留有点数为 i 的牌。

输入格式

第一行两个正整数 n, m。第二行 n 个正整数 a_1 ~ a_n。

输出格式

一行 m 个非负整数，第 i 个表示结束时桌面上留有点数 i 的局数。

输入输出样例

样例 1

4 3
1 2 1 3

输出：

3 1 4

解释：四局的最终桌面分别是 1 3、2 1 3、1 3、3。点数 1 出现在第 1、2、3 局（3 局），点数 2 只在第 2 局（1 局），点数 3 在全部 4 局。

样例 2

10 3
3 1 2 1 3 2 3 1 2 1

输出：

10 3 3

数据范围与约定

• 2 ≤ n ≤ 5×10^5，1 ≤ m ≤ 3×10^5，1 ≤ a_i ≤ m；
• 每种点数至少出现一次；
• 部分测试点牌堆单调不降，或相邻不同的位置很少；
• 原题时限 1.0 秒，内存 1024 MiB。

二、先把四局亲手玩一遍

牌堆 1 2 1 3，n = 4，所以玩 4 局（第 i 局从第 i 张开始打）：

数出 3 1 4。注意第 1 局和第 3 局的结局一模一样——这就是后面所有优化的种子。

三、笨办法的代价

照规则一局局模拟，每局最多打 n 张牌，一共 n 局，需要 n×n 次操作。n 最大 5×10^5：

500000 × 500000 = 250000000000 次（2500 亿次）

电脑 1 秒约做 1 亿次简单操作，这要跑几十分钟，必超时。得找一条「不用一局局玩」的近路。

四、秘密一：盯着每局的第一张牌

第 i 局第一张牌是 a_i，它上来时桌子是空的，一个人站在队伍最左边（队首）。谁能把它请走？只有一种可能：后面又来一张和它点数相同的牌（请人规则是按点数找同款）。所以它只有两种命运。

情况 A：后面还会出现同点数，最近一次在位置 t

• 打到第 t 张之前没有任何同点数牌，谁也动不了队首那张，它一直稳稳站在最左边；
• 打到第 t 张，来了一张一样的 → 找到队首那个同款，把「他和他右边所有人」请走。可他就在队首，他右边就是整支队伍，于是队伍被整个清空，再放上新牌，桌上只剩 [a_t]。

这一刻，桌面和「第 t 局刚打完第一张牌」完全一样，剩下没打的牌也完全一样（都是 a_{t+1} … a_n）。所以后面怎么打，结局完全一样：

第 i 局的结局 = 第 t 局的结局，而且第 i 局没有为桌面贡献任何新牌。像玩游戏读档：前面折腾半天被一键重置，从第 t 局原样重来。

情况 B：后面再也不出现同点数

即 i 是这个点数最后一次出现的位置。队首那张永远没人能请走，它像钉子一样钉在最左边，也不干扰右边发生什么：

第 i 局的结局 = [a_i]（这颗钉子） + 第 i+1 局的结局。

五、秘密二：把 n 局写成一根接力棒

给每个位置 i 定义「把问题交给谁」，记作 f(i)：

因为 f(i) 永远大于 i，所有箭头都指向右边，像一排人把接力棒往右传，最后传到终点 n+1。

关键结论：第 i 局最终的桌面，就是沿着 i → f(i) → f(f(i)) → … → n+1 这条链，把路上所有情况 B 的点数按顺序捡起来。

拿样例 1 验证（a = [1,2,1,3]，f(1)=3、f(2)=3、f(3)=4、f(4)=5）：

有个容易绕晕的地方：第 1 局桌上明明有 1，怎么还说位置 1 不贡献牌？因为那张 1 是位置 3 那颗钉子贡献的（第 1 局被读档到第 3 局了）。我们数的是「哪颗钉子放上去的」，不是「哪一局打了这张牌」。

六、反过来问：谁会经过我

题目问的是「点数 k 出现在多少局的最终桌面上」。把问题倒过来：

点数 k 的最后一次出现位置记作 P（它是唯一能贡献 k 的钉子）。它贡献的那张 k，会出现在哪些局里？→ 所有链条会经过 P 的起点。

把箭头倒过来看，就是一张家谱图：P 有一群「接力棒最终会传到我这里」的起点，这群起点（含 P 自己）的人数就是答案。数据结构里叫子树大小，不用担心这个名词。

怎么数：先发票，再往上交

因为 f(i) > i，有个特别省事的办法：

1. 给每个位置 i 先发 1 张票，代表「第 i 局这个起点自己」；
2. 从 i = 1 到 n 正着走一遍，把 i 手里的票全部交给 f(i)：cnt[f(i)] += cnt[i]；
3. 为什么正着走就行？会交给 i 的位置都比 i 小，它们早就交完了，所以轮到 i 时它手里的票数已经是完整的粉丝团人数；
4. 终点 n+1 是「空桌面」，不是任何一局的起点，初始票数必须是 0。

像收作业：组长先收齐本组，再交给班长，班长收齐全班再交给老师，一遍就够。

七、手算样例 1

第一步：倒着扫，找「右边最近同点数」与「最后一次出现」

第二步：发票 + 正着交票（初始 cnt[1..4] = 1，cnt[5] = 0）

第三步：查表输出

输出 3 1 4，和手工模拟四局一模一样，但一局游戏都没真的玩。

八、为什么一定对

1. 第 i 局第一张牌在队首，只有后面出现同点数才能清掉它：有同点数 ⇒ 结局等于那一局（读档），没有 ⇒ 它钉在队首，结局 = 它 + 下一局的结局；
2. 所以一条链上，只有「最后一次出现」的位置会往桌上放牌，而每个点数恰好只有一个这样的位置；
3. 于是「点数 k 出现在第 i 局桌面」等价于「i 的链条经过 finalPos[k]」，也就是「i 是 finalPos[k] 的粉丝」；粉丝人数由 cnt[f(i)] += cnt[i] 一遍算清。

九、参考代码（AC）

#include <iostream>
#include <vector>
using namespace std;

// 记 R_i 为从第 i 局开始的终局桌面。
// 若 a[i] 在位置 t>i 再次出现，则第 i 局第一张牌一直压在栈底，
// 到 t 打出同点数牌时整个栈被清空为 [a[t]]，此后与第 t 局完全一致，故 R_i = R_t。
// 若 a[i] 不再出现，它永远留在栈底且不影响其它牌，故 R_i = [a[i]] + R_{i+1}。
// 于是每个点数的「贡献源」只有它最后一次出现的位置 P，答案 = 后继树中 P 的子树大小。
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    vector<int> nextSame(n + 2, n + 1), nextAt(m + 1, n + 1), finalPos(m + 1, 0);
    for (int i = n; i >= 1; --i) {
        nextSame[i] = nextAt[a[i]];
        // 右侧不再有同点数牌 => i 就是该点数最后一次出现的位置
        if (nextSame[i] > n) finalPos[a[i]] = i;
        nextAt[a[i]] = i;
    }

    vector<long long> cnt(n + 2, 1);
    cnt[n + 1] = 0;  // 空桌面不是任何一局的贡献源
    for (int i = 1; i <= n; ++i) {
        int fa = nextSame[i] <= n ? nextSame[i] : i + 1;
        cnt[fa] += cnt[i];  // fa > i，正序累加即为拓扑序
    }

    for (int k = 1; k <= m; ++k) {
        if (k > 1) cout << ' ';
        cout << cnt[finalPos[k]];
    }
    cout << '\n';
    return 0;
}

十、代码逐段解析

• 为什么要倒着扫：我们想知道「i 的右边有什么」，所以从最右往左走，边走边把看到的记在小本本 nextAt 上。nextAt[k] = 目前见过的、点数 k 最靠左的位置，正是 i 右边最近的同点数位置；初值 n+1 表示「右边还没有」。走到 i 时先读小本本得到 nextSame[i]，再把小本本更新成 i，留给更左边的位置用。
• nextSame[i] > n 说明右边没同点数，i 就是最后一次出现，记下 finalPos[a[i]] = i。题目保证每种点数至少出现一次，所以每个 finalPos 都会被填好。
• int fa = nextSame[i] <= n ? nextSame[i] : i + 1; 就是 f(i)：有下一次同点数交给它，否则交给 i+1。
• cnt 初始每人 1 张票，终点 n+1 设 0；fa > i 保证正序累加时「先收齐、再上交」。
• 输出时用 if (k > 1) cout << ' '; 控制空格，一行 m 个数。

这里 cnt 最多累到 n = 5×10^5，int 其实装得下；代码统一用 long long 是保险习惯——万一数据范围变大也不会溢出。它和 T2 那个「必须 long long」理由不同，别记混。

十一、复杂度与实测

倒着扫 O(n)、正着交票 O(n)、输出 O(m) ⟹ 时间 O(n + m)，内存 O(n + m)。n = 5×10^5、m = 3×10^5 时约 80 万次操作，最大测试点实测约 0.32 秒（限时 1 秒）。对比笨办法的 2500 亿次，差了约 30 万倍。

十二、易错点清单

1. 别真的一局局模拟，O(n²) 必超时。
2. nextSame 必须是「最近的一次」同点数，不能是任意一次：t 之前若还有同点数，队首早被清空，读档位置就不是 t 了。
3. finalPos 是最后一次出现，不是第一次，这一条最容易搞反。
4. cnt[n+1] = 0：终点不是任何一局的起点，不改成 0 会凭空多算。
5. 必须正序 i = 1 → n 累加，倒序会漏票。
6. 数组开够：a 与 cnt 要 n+2（会用到下标 n+1），nextAt / finalPos 要 m+1（点数是 1~m）。
7. 输出别漏空格，一行 m 个数。
8. 同一时刻桌上同点数最多一张，所以「多少局含 k」才能用粉丝团人数代替逐张数。
9. 每种点数至少出现一次，finalPos 一定非零；若自己改题放宽这条，要处理「该点数没出现过 → 答案 0」。
10. 文件输入输出：原题要求 card.in / card.out，本文代码改用标准输入输出；OJ 提交时请按题目要求加回 freopen。

十三、考点总结

一句话记住：很多局的结局其实一样，找到「读档点」，把 n 局变成一棵接力树，只数一次。

本文题面整理自 CCF CSP-J 2026 第二轮（入门组）试题，题目版权归中国计算机学会所有。题解与代码由椰程信奥整理撰写，参考答案仅供参考，最终以 CCF 官方公布为准。