记录编号	557679	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2020S]函数调用	最终得分	100
用户昵称	锝镆氪锂铽	是否通过	通过
代码语言	C++	运行时间	1.452 s
提交时间	2020-11-21 23:07:42	内存使用	86.14 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#define LL long long
using namespace std;
const int maxN = 1e6 + 10;
const LL MOD = 998244353;

void gettim();
void topologic();

int m, n, Q;
LL a[maxN], v[maxN], mul[maxN], tag[maxN];
int p[maxN], t[maxN], c[maxN], q[maxN];
int in[maxN];
vector <int> G[maxN];
int main(void) {
	freopen("2020call.in", "r", stdin);
	freopen("2020call.out", "w", stdout);
	memset(mul, -1, sizeof(mul));
	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", &t[i]);
		if (t[i] == 1)
			scanf("%d%lld", &p[i], &v[i]);
		else if (t[i] == 2)
			scanf("%lld", &v[i]);
		else {
			scanf("%d", &c[i]);
			for (int j = 0; j < c[i]; j++) {
				int x;
				scanf("%d", &x);
				G[i].push_back(x);
				in[x] ++;
			}
		}
	}
	gettim();
	scanf("%d", &Q);
	for (int i = 1; i <= Q; i++)
		scanf("%d", &q[i]);
	LL rt = 1;
	for (int i = Q; i >= 1; i--) {
		tag[q[i]] = (rt + tag[q[i]]) % MOD;
		rt = rt * mul[q[i]] % MOD;
	}
	for (int i = 1; i <= n; i++)
		a[i] = a[i] * rt % MOD;
	topologic();
	for (int i = 1; i <= n; i++)
		printf("%lld ", a[i]);
	return 0;
}

inline int mod1(int x){
	if (x > MOD)
		x -= MOD;
	return x;
}

inline int mod2(int x) {
	if (x < 0)
		x += MOD;
	return x;
}

inline void add(int& x, int y){
	x = mod1(x + y);
}

inline void sub(int& x, int y){
	x = mod2(x - y);
}

LL dfs(int u) {
	if (mul[u] != -1)
		return mul[u];
	if (!c[u]) {
		if (t[u] == 1)
			mul[u] = 1;
		else
			mul[u] = v[u];
		return mul[u];
	}
	mul[u] = 1;
	for (int i = c[u] - 1; i >= 0; i--) {
		int v = G[u][i];
		mul[u] = mul[u] * dfs(v) % MOD;
	}
	return mul[u];
}

void gettim() {
	for (int i = 1; i <= m; i++)
		if (in[i] == 0)
			dfs(i);
}

void topologic() {
	queue <int> q;
	while (q.size())
		q.pop();
	for (int i = 1; i <= m; i++)
		if (in[i] == 0)
			q.push(i);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		LL rt = 1;
		for (int i = c[x] - 1; i >= 0; i--) {
			int y = G[x][i];
			tag[y] = (tag[y] + rt * tag[x] % MOD) % MOD;
			in[y] --;
			if (in[y] == 0)
				q.push(y);
			rt = rt * mul[y] % MOD;
		}
	}
	for (int i = 1; i <= m; i++)
		if (t[i] == 1)
			a[p[i]] = (a[p[i]] + v[i] * tag[i] % MOD) % MOD;
}