CSP-S 2020 真题 函数调用 题解（提高+/省选-）

CSP-S 2020 这道真题，考点是拓扑排序，我们一步步拆开看。

题目来源：ACGO A34 ｜ 洛谷 P7077难度定位：提高+/省选- ｜ 通过率：69.38%

一、题目信息

题目名称：函数调用

所属赛事：2020 年 CSP-S 组复赛

官方难度：提高+/省选-

涉及知识点：拓扑排序

题目链接：https://www.acgo.cn/problemset/info/34

洛谷编号：P7077（同一道题，两个平台均可提交，代码通用）

易错点（很多人栽在这）

• 排序后原来的下标信息会丢，需要额外记录
• 比较函数的严格弱序要写对，否则排序结果未定义
• 高难度题的暴力分很关键，先写一版能过的部分分再想正解

题意简述

题意其实很直白：

函数是各种编程语言中一项重要的概念，借助函数，我们总可以将复杂的任务分解成一个个相对简单的子任务，直到细化为十分简单的基础操作，从而使代码的组织更加严密、更加有条理。然而，过多的函数调用也会导致额外的开销，影响程序的运行效率。

某数据库应用程序提供了若干函数用以维护数据。已知这些函数的功能可分为三类：

在使用该数据库应用时，用户可一次性输入要调用的函数序列（一个函数可能被调用多次），在依次执行完序列中的函数后，系统中的数据被加以更新。某一天，小 A 在应用该数据库程序处理数据时遇到了困难：由于频繁而低效的函数调用，系统在执行操作时进入了无响应的状态，他只好强制结束了数据库程序。为了计算出正确数据，小 A 查阅了软件的文档，了解到每个函数的具体功能信息，现在他想请你根据这些信息帮他计算出更新后的数据应该是多少。

前置知识

这题要用到的工具不多，但有一个容易忘，先过一遍。

把数据排好再处理

排序本身 O(n log n)，关键是排完之后能利用单调性做线性扫描，把 O(n²) 降到 O(n)。

二、思路分析

这题官方难度提高+/省选-，中场，先拿暴力分比较稳妥。

思路的入口在哪里？

把每个操作和它所执行的操作连单向边，这样就形成了一个 dag。

在这个 dag 上面，真正使答案变化的是那些出度为 0 的点，其他点只是反复地"调用"它们。

那么不难联想到要处理出每一个点所能产生的贡献。

我们发现，对于乘法操作，越靠后进行它影响的范围就越广，而在它之前的所有操作，都受这个乘法的影响。

这样可以沿拓扑序倒序递推出每个节点的贡献，这里的贡献指进行这个操作，整个序列要乘以多少。

接下来我们再考虑加法操作。

同理，你可以维护出对于每个操作，它在这个操作串中被加了多少次。

注意：这时我们就要整体考虑了，并且对于 op≠1 的那些操作，我们递推不是为了统计答案，而是要得到后面状态的值。

很显然，我们要顺着拓扑序去更新。

此时也要把乘法标记下放，最后先乘再加，以防搞混。

三、完整代码

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

// CSP-S 2020 函数调用
// m 个函数，三类：
// 1 t v : a[v] += t
// 2 t : 全体 a[i] *= t
// 3 c g1..gc : 按顺序调用 c 个函数（无环）
// 给定初始 a[1..n] 与执行序列 seq[1..q]，求执行后的 a（模 998244353）。
//
// 思路（经典「超源 + 两次拓扑排序」）：
// 构造 DAG：函数为点，调用关系为有向边（调用者 → 被调用者）。
// 额外加入超源 0 号点代表主程序，它按顺序调用 seq[1..q]。
// ① mul[u]：执行一次 u 会让整个序列整体乘上多少。
// 类型 1 → 1；类型 2 → t；类型 3 → 子函数 mul 之积。
// 在反向图上拓扑合并即可（叶子先出队）。
// ② cnt[u]：函数 u 在最终方案中被执行的等效次数（已含外层「位于其后的乘法」）。
// cnt[0] = 1，其余为 0。在正向图上按拓扑序下放：
// · 对类型 3 或超源：**倒序**遍历其子函数：
// run = cnt[u];
// for j = 末..0: cnt[child[j]] += run; run = run * mul[child[j]];
// 因为排在后面的兄弟函数里的乘法会放大前面兄弟的执行效果。
// ③ 答案：a[i] = a[i] * mul[0] + Σ_{类型 1 且 pos=i} t * cnt[u]（模）。
const long long MOD = 998244353;
const int MAXN = 100005;

int n, m, q;
long long a[MAXN];
int tp[MAXN]; // 函数类型；超源 tp[0]=3
int posi[MAXN]; // 类型 1 的位置
long long val[MAXN]; // 类型 1 的值 / 类型 2 的乘数
long long mulv[MAXN]; // 整体乘数
long long cntv[MAXN]; // 等效执行次数
vector<int> rev_[MAXN]; // 反向图：rev_[u] = u 的所有父节点
vector<int> fwd[MAXN]; // 正向图：fwd[u] = u 调用的子函数
int outdeg[MAXN]; // 正向出度（= 反向图入度）
int indeg_[MAXN]; // 正向入度（= 反向图出度）

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
scanf("%d", &m);
for (int i = 1; i <= m; ++i) {
scanf("%d", &tp[i]);
mulv[i] = 1;
if (tp[i] == 1) {
scanf("%d %lld", &posi[i], &val[i]);
} else if (tp[i] == 2) {
scanf("%lld", &val[i]);
mulv[i] = val[i] % MOD;
} else {
int c; scanf("%d", &c);
for (int j = 0; j < c; ++j) {
int g; scanf("%d", &g);
fwd[i].push_back(g);
rev_[g].push_back(i);
outdeg[i]++; indeg_[g]++;
}
}
}
scanf("%d", &q);
tp[0] = 3; mulv[0] = 1; cntv[0] = 1;
for (int i = 0; i < q; ++i) {
int f; scanf("%d", &f);
fwd[0].push_back(f);
rev_[f].push_back(0);
outdeg[0]++; indeg_[f]++;
}

// ———- ① 反向拓扑求 mul ———-
{
static int deg[MAXN];
for (int i = 0; i <= m; ++i) deg[i] = outdeg[i]; // 反向图入度
queue<int> Q;
for (int i = 0; i <= m; ++i) if (deg[i] == 0) Q.push(i);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
for (size_t k = 0; k < rev_[u].size(); ++k) {
int p = rev_[u][k];
mulv[p] = mulv[p] * mulv[u] % MOD; // 父节点累乘子函数
if (–deg[p] == 0) Q.push(p);
}
}
}

// ———- ② 正向拓扑求 cnt ———-
{
static int deg[MAXN];
for (int i = 0; i <= m; ++i) deg[i] = indeg_[i];
queue<int> Q;
for (int i = 0; i <= m; ++i) if (deg[i] == 0) Q.push(i);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
if (u == 0 || tp[u] == 3) {
long long run = cntv[u] % MOD;
for (int j = (int)fwd[u].size() – 1; j >= 0; –j) {
int v = fwd[u][j];
cntv[v] = (cntv[v] + run) % MOD;
run = run * mulv[v] % MOD;
if (–deg[v] == 0) Q.push(v);
}
} else {
for (size_t j = 0; j < fwd[u].size(); ++j) {
int v = fwd[u][j];
if (–deg[v] == 0) Q.push(v);
}
}
}
}

// ———- ③ 汇总 ———-
for (int i = 1; i <= n; ++i) a[i] = a[i] % MOD * mulv[0] % MOD;
for (int u = 1; u <= m; ++u)
if (tp[u] == 1)
a[posi[u]] = (a[posi[u]] + val[u] % MOD * cntv[u]) % MOD;

for (int i = 1; i <= n; ++i) printf("%lld%c", a[i], i == n ? '\\n' : ' ');
return 0;
}

四、代码分段拆解

完整代码在上面，下面按功能分块解释。

头文件与全局变量

先把用到的头文件和全局变量放上来。全局变量在竞赛里很常用，好处是函数之间共享方便，代价是要小心初始化和被意外改写。

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const long long MOD = 998244353;
const int MAXN = 100005;
int n, m, q;
long long a[MAXN];
int tp[MAXN]; // 函数类型；超源 tp[0]=3
int posi[MAXN]; // 类型 1 的位置
long long val[MAXN]; // 类型 1 的值 / 类型 2 的乘数
long long mulv[MAXN]; // 整体乘数
long long cntv[MAXN]; // 等效执行次数
vector<int> rev_[MAXN]; // 反向图：rev_[u] = u 的所有父节点
vector<int> fwd[MAXN];

主体逻辑

主体部分按顺序完成读入、计算、输出。main 函数尽量保持线性，把复杂的逻辑拆成独立函数，出问题时更容易定位。

五、实例模拟

光看代码容易虚，用样例实测一遍最踏实。

样例 1

输入：

3
1 2 3
3
1 1 1
2 2
3 2 1 2
2
2 3

输出：

6 8 12

样例 2

输入：

10
1 2 3 4 5 6 7 8 9 10
8
3 2 2 3
3 2 4 5
3 2 5 8
2 2
3 2 6 7
1 2 5
1 7 6
2 3
3
1 2 3

输出：

36 282 108 144 180 216 504 288 324 360

以第一组样例为例，输入是 3、1 2 3、3、1 1 1、2 2、3 2 1 2、2、2 3，正确输出是 6 8 12。建议把这两行数据抄在纸上，用上面的代码手动走一遍，重点看循环变量怎么变化、答案在哪一步被更新。能自己推出来的东西，比看懂代码印象深得多。

六、踩坑总结

最后总结几个要点。

另外提醒一句：这题在 CSP-S 2020 里是提高+/省选-难度，考场上如果没有把握拿满分，先把暴力写法交上去拿到部分分，再回头优化。CSP 是打分制，空着不写才是最亏的。

七、知识点拓展

这题的核心是排序。

排序是所有算法的基础设施。很多看起来复杂的问题，排完序之后就变成了线性扫描。

建议的练习路径：

八、适用人群

这道题的适用面：

• 目标是 CSP-S 高分或省选的同学
• 想通过真题理解高难度题如何从暴力优化到正解的同学
• 想弄明白排序类问题标准解法的同学

代码有任何问题欢迎指正，我会及时更新。

关于这个系列

这是「CSP 真题逐题精讲」的第 16 篇。我会按年份从 2019 一路刷到 2025，CSP-J 和 CSP-S 全覆盖。每篇都给：双平台题号（ACGO + 洛谷）+ 逐行代码拆解 + 真实样例模拟。

跟着刷完这一套，CSP 第一轮的选择题和基础题基本就稳了。

下一篇：CSP-S 2020 动物园（普及/提高-）

👉 关注我，不错过后续更新。评论区告诉我你现在刷到哪一年了，我看看能不能按大家的进度调整更新节奏。