ARTICLE · 1300595

真题解析:P17830 [CSP-J 2026] 纸牌游戏(逆序递推·最后出现位置·隐式树·子树大小·64位整型)

发布时间：2026-11-03 09:46:17 最近访问：2026-11-03 09:46:17

题目来源：洛谷 P17830 [CSP-J 2026] 纸牌游戏 / card

题目大意

有一叠纸牌共 n 张，从上到下的点数依次为 a[1], a[2], …, a[n]，每个点数都在 1 到 m 之间，且每种点数至少出现一次。

一共进行 n 局相互独立的游戏。第 i 局跳过前 i − 1 张牌，依次打出 a[i], a[i+1], …, a[n]。桌面上的牌始终从左到右排成一行。打出一张点数为 x 的牌时：

• 桌面上没有 x：把这张牌放到最右端；
• 桌面上已经有 x：把桌面上那张 x 以及它右侧的所有牌全部收走，再把新打出的 x 放到最右端。

要求输出 m 个数，第 v 个数表示：在全部 n 局游戏中，有多少局结束时桌面上留有点数为 v 的牌。

数据范围：2 ≤ n ≤ 5×10⁵，1 ≤ m ≤ 3×10⁵，1 ≤ a[i] ≤ m。特殊性质 A：a 单调不降；特殊性质 B：至多 4999 个 i 满足 a[i] ≠ a[i+1]。

输入输出样例

样例输入 #1

4 31 2 1 3

样例输出 #1

3 1 4

样例输入 #2

10 33 1 2 1 3 2 3 1 2 1

样例输出 #2

10 3 3

样例 1 的四局桌面依次是 {1, 3}、{2, 1, 3}、{1, 3}、{3}，所以点数 1 出现在 3 局、点数 2 出现在 1 局、点数 3 出现在 4 局。

考点梳理

考点	在本题里的作用
后缀不变性	某一局的桌面只由少数几个「关键位置」决定，中间过程全部作废
逆序扫描	从 n 往 1 扫，第一次遇到某个点数就是它的最后出现位置
最后出现位置 lastp	判断一张牌「还会不会被顶掉」的唯一依据
隐式树（父指针数组）	每个位置只有一条出边且指向更大下标，天然构成以 n + 1 为根的树
子树大小统计	把「有多少局的桌面含这张牌」转成「这棵子树有多少个结点」
正序累加替代 DFS	儿子下标必小于父亲，按下标从小到大扫一遍即完成子树求和，不会爆栈
64 位整型	答案累加量级可达 10¹¹，int 会溢出

解题思路

一、暴力模拟为什么必然超时

最直接的做法是枚举每一局起点 i，用一个栈维护当前桌面：打出 x 时若栈里已有 x，就把它右侧的牌全部弹出，再把 x 压入；一局结束后把栈里每个点数计入答案。

单局 O(n)，n 局就是 O(n²)。n = 5×10⁵ 时约 2.5×10¹¹ 次基本操作，1 秒的时限里跑不完。样例规模小，随手测都能过，一交大数据就 TLE——这也是本题最常见的失分方式。

要降复杂度，只能让 n 局共享同一份信息。换个问法：不问「这一局打到某一步时桌面长什么样」，改问「这一局的最终桌面，由哪些位置决定」。

二、观察一：每一局的第一张牌，一定留到自己这局结束

第 i 局的第一张牌是 a[i]，它躺在桌面最左端。

收走动作永远只收「某个点数以及它右侧的牌」，最左端没有任何牌在它左边。之后打出的点数不等于 a[i] 时，被收走的是别的点数及其右侧，动不到它；打出的点数等于 a[i] 时，被收走的是桌面上那张旧 a[i] 及其右侧，但随即新打出的 a[i] 又被放到最右端，点数 a[i] 依然在桌面上。

所以第 i 局的最终桌面一定包含 a[i]。桌面可以拆成两层：底层固定是 a[i]，上层是 a[i] 之后那些牌演化出来的结果。接下来只需要搞清楚「a[i] 之后的结果是什么」。

三、观察二：i 之后的结果，只由 lastp[a[i]] 决定

记 lastp[v] 为点数 v 在整个序列里最后一次出现的下标，l = lastp[a[i]]。分两种情况。

l = i。 i 就是 a[i] 的最后一次出现，本局后面不会再打出这个点数，底层那张 a[i] 从此不参与任何收走动作。它上方的演化与「从 i+1 单独开一局」完全一致。

l > i。 i 到 l 之间可能打出很多牌，但在 l 处打出同点数时，底层那张 a[i] 被匹配，它右侧的所有牌被一并收走，桌面塌缩成单独一张 a[i]。而 l 之后 a[i] 不再出现，上方的演化与「从 l+1 单独开一局」完全一致。

两种情况合起来只有一条递推：

to[i] = (lastp[a[i]] > i) ? lastp[a[i]] + 1 : i + 1

于是第 i 局的最终桌面，就是 i → to[i] → to[to[i]] → … 这条链上所有位置对应的点数。

这里有个容易被忽略的点：跳的是 lastp[a[i]]，而不是「下一次出现的位置」。i 到 l 之间那些同点数出现处，桌面被反复清空又重建，最终的贡献全部被 l 处那一次收走吞掉，整段都是无效状态，跳过去不会丢任何信息。反过来，如果跳到「下一次出现位置 + 1」，就会把注定被清空的中间段当成有效桌面，答案偏大。

链上位置的点数两两不同，这也正好对应「桌面上同一种点数至多一张」：因为 to[i] 落在 l 之后，而 l 已经是 a[i] 的最后一次出现，所以链在 i 之后再也不会碰到点数 a[i]。

四、观察三：所有链拼成一棵以 n + 1 为根的树

对每个位置 i 连一条边 i → to[i]。无论哪种情况都有 to[i] > i，所以所有边都指向更大的下标，整张图是一棵以 n + 1 为根的有向树，n + 1 是不对应任何纸牌的哨兵。

由此，第 i 局的桌面 = i 到根的路径上的所有位置。

反过来问：某个固定位置 p，会出现在多少局的桌面上？只要 p 是 i 的祖先，第 i 局的桌面就含 p；而「p 是 i 的祖先」等价于「i 落在 p 的子树里」。所以位置 p 出现的局数，恰好是 p 的子树大小 sz[p]。

五、正序累加求子树大小，不用 DFS

按常规做法应该 DFS 求子树大小，但链长可以达到 n = 5×10⁵，递归深度同样能到 5×10⁵，直接爆栈。

注意到 to[i] > i：父亲的下标一定大于儿子。那么把下标从小到大当成拓扑序即可。sz[i] 初值为 1，按 i = 1, 2, …, n 的顺序执行 sz[to[i]] += sz[i]。轮到 i 时，所有以 i 为父的位置（下标都小于 i）早已把贡献加进来了，一次线性扫描就能算出全部子树大小。

六、按点数汇总

位置 p 的贡献是 sz[p]，它对答案的作用是「点数 a[p] 多被 sz[p] 局看到」，所以直接累加 ans[a[p]] += sz[p]，最后输出 ans[1] 到 ans[m]。

以样例 2 走一遍，a = 3 1 2 1 3 2 3 1 2 1。

先逆序扫出 lastp：点数 1 最后出现在 10，点数 2 最后出现在 9，点数 3 最后出现在 7。

再算 to 与累加 sz：

i	a[i]	lastp[a[i]]	to[i]	累加后
1	3	7	8	sz[8] = 2
2	1	10	11	sz[11] = 2
3	2	9	10	sz[10] = 2
4	1	10	11	sz[11] = 3
5	3	7	8	sz[8] = 3
6	2	9	10	sz[10] = 3
7	3	7	8	sz[8] = 4
8	1	10	11	sz[11] = 7
9	2	9	10	sz[10] = 4
10	1	10	11	sz[11] = 11

得到 sz[8] = 4（子树 {8, 1, 5, 7}）、sz[10] = 4（子树 {10, 3, 6, 9}）、sz[11] = 11，其余位置都是 1。

汇总时按位置逐个累加 ans[a[i]] += sz[i]：点数 3 出现在位置 1、5、7，三处 sz 都是 1，故 ans[3] = 3；点数 2 出现在位置 3、6、9，sz 也都是 1，故 ans[2] = 3；点数 1 出现在位置 2、4、8、10，其中 2 和 4 的 sz 为 1、8 和 10 的 sz 为 4，故 ans[1] = 1 + 1 + 4 + 4 = 10。输出 10 3 3，与样例一致。

顺手验一局。起点 i = 1，链是 1 → 8 → 11，桌面点数为 {a[1], a[8]} = {3, 1}。实模一遍：3 入栈，桌面 [3]；1 入栈，[3, 1]；2 入栈，[3, 1, 2]；再打 1，收走 2，[3, 1]；打 3，收走 3 及其右侧，[3]；2 入栈，[3, 2]；打 3，收走 2，[3]；1 入栈，[3, 1]；2 入栈，[3, 1, 2]；打 1，收走 2，得到 [3, 1]。与链上的点数一致。

参考代码

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 500005;int n, m, a[N], lastp[N], to[N];ll sz[N], ans[N];int main(){    ios::sync_with_stdio(false);    cin.tie(0);    cin >> n >> m;    for (int i = 1; i <= n; i++) cin >> a[i];    for (int i = n; i >= 1; i--) if (!lastp[a[i]]) lastp[a[i]] = i;    for (int i = 1; i <= n; i++) sz[i] = 1;    for (int i = 1; i <= n; i++) {        to[i] = lastp[a[i]] > i ? lastp[a[i]] + 1 : i + 1;        sz[to[i]] += sz[i];    }    for (int i = 1; i <= n; i++) ans[a[i]] += sz[i];    for (int i = 1; i <= m; i++) cout << ans[i] << (i == m ? '\n' : ' ');    return 0;}