2010：【20CSPS提高组】函数调用
时间限制: 2000 ms 内存限制: 262144 KB
提交数: 351 通过数: 125
【题目描述】
函数是各种编程语言中一项重要的概念，借助函数，我们总可以将复杂的任务分解成一个个相对简单的子任务，直到细化为十分简单的基础操作，从而使代码的组织更加严密、更加有条理。然而，过多的函数调用也会导致额外的
开销，影响程序的运行效率。
某数据库应用程序提供了若干函数用以维护数据。已知这些函数的功能可分为三类：
1. 将数据中的指定元素加上一个值；
2. 将数据中的每一个元素乘以一个相同值；
3. 依次执行若干次函数调用，保证不会出现递归（即不会直接或间接地调用本身）。
在使用该数据库应用时，用户可一次性输入要调用的函数序列（一个函数可能被调用多次），在依次执行完序列中的函数后，系统中的数据被加以更新。
某一天，小 A 在应用该数据库程序处理数据时遇到了困难：由于频繁而低效的函数调用，系统在执行操作时进入了无响应的状态，他只好强制结束了数据库程序。为了计算出正确数据，小 A 查阅了软件的文档，了解到每个函数的具体功能信息，现在他想请你根据这些信息帮他计算出更新后的数据应该是多少。
【输入】
第 1 行一个正整数 n，表示数据的个数。
第 2 行 n 个整数，第 i 个整数表示下标为 i 的数据的初始值为 ai。
第 3 行一个正整数 m，表示数据库应用程序提供的函数个数。函数从 1∼m 编号。
接下来 m 行中，第 j（1≤j≤m）行的第一个整数为 Tj，表示 j 号函数的类型：
1. 若 Tj=1，接下来两个整数 pj,vj 分别表示要执行加法的元素的下标及其增加的值；
2. 若 Tj=2，接下来一个整数 vj 表示所有元素所乘的值；
3. 若 Tj=3，接下来一个正整数 cj 表示 j 号函数要调用的函数个数，随后 cj 个整数 g(j)1,g(j)2,...,g(j)cj依次表示其所调用的函数的编号。
第 m + 4 行一个正整数 Q，表示输入的函数操作序列长度。
第 m + 5 行 Q 个整数 fi，第 i 个整数表示第 i 个执行的函数的编号。
【输出】
一行 n 个用空格隔开的整数，按照下标 1∼n 的顺序，分别输出在执行完输入的函数序列后，数据库中每一个元素的值。答案对 998244353 取模。
【输入样例】
3
1 2 3
3
1 1 1
2 2
3 2 1 2
2
2 3
【输出样例】
6 8 12
【提示】
6 8 12
【提示】
【样例 1 解释】
1 号函数功能为将 a1 的值加一。2 号函数功能为所有元素乘 2。3 号函数将先调用 1 号函数，再调用 2 号函数。
最终的函数序列先执行 2 号函数，所有元素的值变为 2,4,6。
再执行 3 号函数时，先调用 1 号函数，所有元素的值变为 3,4,6。再调用 2号函数，所有元素的值变为 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
【样例 2 输出】
36 282 108 144 180 216 504 288 324 360
| 测试点编号 | n, m,Q ≤ | ∑cj | 其他特殊限制 |
| 1~2 | 1000 | = m-1 | 函数调用关系构成一棵树 |
| 3~4 | ≤ 100 | 无 | |
| 5~6 | 20000 | ≤ 40000 | 不含第 2 类函数或不含第 1 类函数 |
| 7 | = 0 | 无 | |
| 8~9 | = m − 1 | 函数调用关系构成一棵树 | |
| 10~11 | ≤ 2×105 | 无 | |
| 12~13 | 105 | 不含第 2 类函数或不含第 1 类函数 | |
| 14 | = 0 | 无 | |
| 15~16 | = m − 1 | 函数调用关系构成一棵树 | |
| 17~18 | ≤ 5×105 | 无 | |
| 19~20 | ≤ 106 |
对于所有数据：0≤ai≤104，Tj∈{1,2,3}，1≤pj≤n，0≤vj≤104，1≤g(j)k≤m，1≤fi≤m。
代码：
#include暑期编程PK赛 得CSDN机械键盘等精美礼品！#define N 1000005 using namespace std; typedef long long ll; template inline void read(T &num) { T x = 0; char ch = getchar(); for (; ch > '9' || ch < '0'; ch = getchar()); for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0'); num = x; } const ll mod = 998244353; int n, m, Q, F[N]; int head[N], pre[N<<1], to[N<<1], sz, inde[N]; ll a[N]; inline void addedge(int u, int v) { pre[++sz] = head[u]; head[u] = sz; to[sz] = v; inde[v]++; } struct oper { int tp, p; ll v, mul, sum; } b[N]; queue q; int ord[N], bnbn; void toposort() { //拓扑排序 for (int i = 1; i <= m; i++) if (!inde[i]) q.push(i); while (!q.empty()) { int x = q.front(); q.pop(); ord[++bnbn] = x; for (int i = head[x]; i; i = pre[i]) { int y = to[i]; inde[y]--; if (!inde[y]) q.push(y); } } } void getmul() { //计算节点的mul for (int i = m; i; i--) { int x = ord[i]; for (int j = head[x]; j; j = pre[j]) { int y = to[j]; b[x].mul = b[x].mul * b[y].mul % mod; } } } void getsum() { //下传节点的sum for (int i = 1; i <= m; i++) { int x = ord[i]; ll now = 1; for (int j = head[x]; j; j = pre[j]) { int y = to[j]; b[y].sum = (b[y].sum + b[x].sum * now % mod) % mod; now = now * b[y].mul % mod; } } } int main() { read(n); for (int i = 1; i <= n; i++) read(a[i]); read(m); for (int i = 1; i <= m; i++) { read(b[i].tp); if (b[i].tp == 1) { read(b[i].p); read(b[i].v); b[i].mul = 1; } else if (b[i].tp == 2) { read(b[i].v); b[i].mul = b[i].v; } else { read(b[i].p); b[i].mul = 1; for (int j = 1, x; j <= b[i].p; j++) { read(x); addedge(i, x); } } } toposort(); getmul(); read(Q); ll now = 1; for (int i = 1; i <= Q; i++) read(F[i]); for (int i = Q; i; i--) { int x = F[i]; b[x].sum = (b[x].sum + now) % mod; now = now * b[x].mul % mod; } getsum(); for (int i = 1; i <= n; i++) a[i] = a[i] * now % mod; for (int i = 1; i <= m; i++) { if (b[i].tp == 1) { a[b[i].p] = (a[b[i].p] + b[i].v * b[i].sum % mod) % mod; } } for (int i = 1; i <= n; i++) printf("%lld ", a[i]); return 0; }
