鄭姐

非常厲害的題目，又是一些注意力+可能算一點的正反則難

不會做，怎麼辦？

考慮特殊性質，不包含$3$操作

線段樹？ 複雜度楊威了，不可行

我們考慮手玩樣例，考慮一個數$x$先$+1$ 、 $\times 2$ 、 $+3$最後$\times 4$

則可以表示成：

我們把它展開

我們注意到我們每一個加的數$add_i$啊，最終的答案一定是乘上整個過程的尾碼的

所以說我們可以**倒著處理！ **

然後考慮有操作$3$的操作 首先不會產生遞迴，一定是一個DAG，所以可以建圖

然後因為每次調用一個操作$3$一定會進行很多次操作，所以考慮預處理

拓撲排序或者使用dfs來預處理，使用$mul_i$表示我們完成了$i$之後整個序列會乘為原來多少倍，由此我們就處理完了我們使用操作$3$調用含有操作$2$的操作

首先可以考慮把乘法操作融合進加法操作中，只需要記錄變成原來多少倍就好

我們用$dp_i$表示調用函數$i$之後整個數組被乘上了$dp_i$倍，所以我們需要倒著處理

但是這個$dp_i$和剛才的$mul_i$又不是一回事，$mul_i$是單獨處理圖上的東西，但是$dp_i$是在倒著的時候包含$mul_i$的，因為$dp_i$我們算完之後就要開始計算答案了

算完之後我們應該記一個變數$Mu$表示在倒著處理所有操作的時候當前到了第$i$個，整個數組被乘上了$Mu$倍，這個東西是輔助$dp_i$進行計算的

我們用$f$表示當前倒數第$i$個函數是什麼

1. 考慮第一種操作，因為是僅僅有加法操作，可以直接讓 $dp_f+Mu$

2. 第二種操作因為又有了乘法操作，但是乘法操作是已經給別的東西貢獻了，也就是說我們已經把乘法操作融合進了別的操作裡面，例如$dp_i$是幹什麼用的，所以我們直接讓$Mu\times V_f$

3. 第三個就是$3$操作，這個東西因為裡面可能包含著加法，但是又會有乘法，所以要讓$dp_f+Mu$且$Mu \times mul_f$

然後我們再進行一次拓撲排序，但是這次雖然是正著，但是每一個點$u$其中的連邊順序是要倒著進行拓撲排序

在拓撲排序的時候我們處理每一個$add_i$，因為我們每個東西的多少倍已經求出來了，所以直接讓$add_i=add_i+dp_u\times V_u$ 這是為什麼呢？ 因為我們要處理$3$操作中的加法操作，做如下處理：

讓$dp_u+dp_v$且$mul_u \times mul_v$這裡的$mul_u$不是真正的$mul_u$而是一個變數

最後答案就是$a_i\times Mu+add_i$

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<queue>
#define int long long
using namespace std;
bool Test_MLE_start;
constexpr int N=1e5+10,mod=998244353;
int _=1,n,m,Q,Mu=1,p[N],func[N],opt[N],ind[N],dp[N],mul[N],Add[N];
bool vis[N];queue<int> q;vector<int> ve[N];
struct node{int p,v;}x[N];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
inline void files(){
	freopen("std.in","r",stdin);
	freopen("std.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
void add(int u,int v){ve[u].push_back(v),ind[v]++;}
void dfs(int u){
	vis[u]=1,mul[u]=(opt[u]==2?x[u].v:1);
	for(auto v:ve[u]){
		if(!vis[v]) dfs(v);
		mul[u]=mul[u]*mul[v]%mod;
	}
}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads();
		for(int i=1;i<=n;i++) p[i]=reads();m=reads();
		for(int i=1;i<=m;i++){
			opt[i]=reads();
			if(opt[i]==1) x[i].p=reads(),x[i].v=reads();
			else if(opt[i]==2) x[i].v=reads();
			else{
				int cj=reads();
				for(int j=1;j<=cj;j++){
					int v=reads();
					add(i,v);
				}
			}
		}Q=reads();
		for(int i=1;i<=Q;i++) func[i]=reads();
		for(int i=1;i<=m;i++) if(!vis[i]&&!ind[i]) dfs(i);
		for(int i=Q;i>=1;i--){
			int f=func[i];
			if(opt[f]==1) dp[f]=(dp[f]+Mu)%mod;
			else if(opt[f]==2) Mu=(Mu*x[f].v)%mod;
			else dp[f]=(dp[f]+Mu)%mod,Mu=(Mu*mul[f])%mod;
		}for(int i=1;i<=m;i++) if(!ind[i]) q.push(i);
		while(!q.empty()){
			int u=q.front(),wy=dp[u];q.pop();
			if(opt[u]==1) Add[x[u].p]=(Add[x[u].p]+dp[u]*x[u].v);
			reverse(ve[u].begin(),ve[u].end());
			for(auto v:ve[u]){
				if(!(--ind[v])) q.push(v);
				dp[v]=(dp[v]+wy)%mod,wy=(wy*mul[v])%mod;
			}
		}for(int i=1;i<=n;i++) printf("%lld ",(p[i]*Mu+Add[i])%mod);
	}
	return 0;
}

郑姐

非常厉害的题目，又是一些注意力+可能算一点的正反则难

不会做，怎么办？

考虑特殊性质，不包含 $3$ 操作

线段树？复杂度杨威了，不可行

我们考虑手玩样例，考虑一个数 $x$ 先 $+1$ 、 $\times 2$ 、$+3$ 最后 $\times 4$

则可以表示成：

我们把它展开

我们注意到我们每一个加的数 $add_i$ 啊，最终的答案一定是乘上整个过程的后缀的

所以说我们可以倒着处理！

然后考虑有操作 $3$ 的操作

首先不会产生递归，一定是一个DAG，所以可以建图

然后因为每次调用一个操作 $3$ 一定会进行很多次操作，所以考虑预处理

拓扑排序或者使用dfs来预处理，使用 $mul_i$ 表示我们完成了 $i$ 之后整个序列会乘为原来多少倍，由此我们就处理完了我们使用操作 $3$ 调用含有操作 $2$ 的操作

首先可以考虑把乘法操作融合进加法操作中，只需要记录变成原来多少倍就好

我们用 $dp_i$ 表示调用函数 $i$ 之后整个数组被乘上了 $dp_i$ 倍，所以我们需要倒着处理

但是这个 $dp_i$ 和刚才的 $mul_i$ 又不是一回事， $mul_i$ 是单独处理图上的东西，但是 $dp_i$ 是在倒着的时候包含 $mul_i$ 的，因为 $dp_i$ 我们算完之后就要开始计算答案了

算完之后我们应该记一个变量 $Mu$ 表示在倒着处理所有操作的时候当前到了第 $i$ 个，整个数组被乘上了 $Mu$ 倍，这个东西是辅助 $dp_i$ 进行计算的

我们用 $f$ 表示当前倒数第 $i$ 个函数是什么

1. 考虑第一种操作，因为是仅仅有加法操作，可以直接让 $dp_f+Mu$

2. 第二种操作因为又有了乘法操作，但是乘法操作是已经给别的东西贡献了，也就是说我们已经把乘法操作融合进了别的操作里面，例如 $dp_i$ 是干什么用的，所以我们直接让 $Mu\times V_f$

3. 第三个就是 $3$ 操作，这个东西因为里面可能包含着加法，但是又会有乘法，所以要让 $dp_f+Mu$ 且 $Mu \times mul_f$

然后我们再进行一次拓扑排序，但是这次虽然是正着，但是每一个点 $u$ 其中的连边顺序是要倒着进行拓扑排序

在拓扑排序的时候我们处理每一个 $add_i$ ，因为我们每个东西的多少倍已经求出来了，所以直接让 $add_i=add_i+dp_u\times V_u$

这是为什么呢？因为我们要处理 $3$ 操作中的加法操作，做如下处理：

让 $dp_u+dp_v$ 且 $mul_u \times mul_v$ 这里的 $mul_u$ 不是真正的 $mul_u$ 而是一个变量

最后答案就是 $a_i\times Mu+add_i$

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<queue>
#define int long long
using namespace std;
bool Test_MLE_start;
constexpr int N=1e5+10,mod=998244353;
int _=1,n,m,Q,Mu=1,p[N],func[N],opt[N],ind[N],dp[N],mul[N],Add[N];
bool vis[N];queue<int> q;vector<int> ve[N];
struct node{int p,v;}x[N];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
inline void files(){
	freopen("std.in","r",stdin);
	freopen("std.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
void add(int u,int v){ve[u].push_back(v),ind[v]++;}
void dfs(int u){
	vis[u]=1,mul[u]=(opt[u]==2?x[u].v:1);
	for(auto v:ve[u]){
		if(!vis[v]) dfs(v);
		mul[u]=mul[u]*mul[v]%mod;
	}
}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads();
		for(int i=1;i<=n;i++) p[i]=reads();m=reads();
		for(int i=1;i<=m;i++){
			opt[i]=reads();
			if(opt[i]==1) x[i].p=reads(),x[i].v=reads();
			else if(opt[i]==2) x[i].v=reads();
			else{
				int cj=reads();
				for(int j=1;j<=cj;j++){
					int v=reads();
					add(i,v);
				}
			}
		}Q=reads();
		for(int i=1;i<=Q;i++) func[i]=reads();
		for(int i=1;i<=m;i++) if(!vis[i]&&!ind[i]) dfs(i);
		for(int i=Q;i>=1;i--){
			int f=func[i];
			if(opt[f]==1) dp[f]=(dp[f]+Mu)%mod;
			else if(opt[f]==2) Mu=(Mu*x[f].v)%mod;
			else dp[f]=(dp[f]+Mu)%mod,Mu=(Mu*mul[f])%mod;
		}for(int i=1;i<=m;i++) if(!ind[i]) q.push(i);
		while(!q.empty()){
			int u=q.front(),wy=dp[u];q.pop();
			if(opt[u]==1) Add[x[u].p]=(Add[x[u].p]+dp[u]*x[u].v);
			reverse(ve[u].begin(),ve[u].end());
			for(auto v:ve[u]){
				if(!(--ind[v])) q.push(v);
				dp[v]=(dp[v]+wy)%mod,wy=(wy*mul[v])%mod;
			}
		}for(int i=1;i<=n;i++) printf("%lld ",(p[i]*Mu+Add[i])%mod);
	}
	return 0;
}

部分分

20分做法

#1~4

按照题意模拟递归的过程即可。

30分做法

#7,14

没有 3 操作，考虑每一个加法的贡献，就是他后边乘了多少。

40分做法

#5,6,12,13

【不含第 2 类函数或不含第 1 类函数】，

其中 #5,6 【不含第 1 类函数】；#12,13【不含第 2 类函数】。

其中 #5,6， 由于乘法是全局的，所以直接一遍拓扑即可。

以下是整合代码

#include<bits/stdc++.h>
#define R(x) x=read()
#define int long long
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e-'0');
		e=getchar();
	}
	return x*y;
}
const int N=100005,mod=998244353;
int n,m,a[N],q,f[N];
int mul[N];
int ind[N];
vector<int>G[N];
vector<int>g[N];
struct node {
	int opt,p,v;
} fun[N];
//for 10 pts
int laz[N];

//for 20 pts
void work(int u) {
	int opt=fun[u].opt,p=fun[u].p,v=fun[u].v;
	if(opt==1) {
		a[p]=(a[p]+v)%mod;
	} else if(opt==2) {
		for(int i=1; i<=n; ++i) a[i]=a[i]*v%mod;
	} else {
		for(auto v:G[u]) work(v);
	}
}
//for 20 pts

queue<int>Q;
signed main() {
//	freopen("call.in","r",stdin);
//	freopen("call.out","w",stdout);
	R(n);
	for(int i=1; i<=n; ++i) {
		R(a[i]);
	}
	bool flag1=0,flag2=0,flag3=0;
	R(m);
	for(int i=1; i<=m; ++i) {
		int R(op);
		if(op==1) {
			int R(p),R(v);
			fun[i]= {1,p,v};
			flag1=1;
		} else if(op==2) {
			int R(v);
			fun[i]= {2,0,v};
			flag2=1;
		} else {
			int R(c);
			fun[i]= {3,0,0};
			while(c--) {
				int R(x);
				G[i].push_back(x);
				g[x].push_back(i);
				++ind[i];
			}
			flag3=1;
		}
	}
	R(q);
	for(int i=1; i<=q; ++i) {
		R(f[i]);
	}
	if(!flag1) {
		for(int i=1; i<=n; ++i) {
			mul[i]=1;
			if(!ind[i])Q.push(i),mul[i]=fun[i].v;
		}
		while(!Q.empty()) {
			int u=Q.front();
			Q.pop();
			for(auto v:g[u]) {
				mul[v]=mul[v]*mul[u]%mod;
				if(!(--ind[v]))Q.push(v);
			}
		}
		int mulll=1;
		for(int i=1; i<=q; ++i) {
			mulll=mulll*mul[f[i]]%mod;
		}
		for(int i=1; i<=n; ++i) {
			a[i]=a[i]*mulll%mod;
			cout<<a[i]<<" ";
		}
		return 0;
	}
	if(!flag3) {
		for(int i=1; i<=q+1; ++i) mul[i]=1;
		for(int i=q; i>=1; --i) {
			mul[i]=mul[i+1];
			if(fun[f[i]].opt==2) {
				mul[i]=mul[i]*fun[f[i]].v%mod;
			}
		}
		for(int i=1; i<=n; ++i)a[i]=a[i]*mul[1]%mod;
		for(int i=1; i<=q; ++i) {
			if(fun[f[i]].opt==1) {
				int p=fun[f[i]].p,v=fun[f[i]].v;
				a[p]=(a[p]+v*mul[i]%mod)%mod;
			}
		}
		for(int i=1; i<=n; ++i) {
			cout<<a[i]<<" ";
		}
		return 0;
	}
	if(n<=1000) {
		for(int i=1; i<=q; ++i) {
			work(f[i]);
		}
		for(int i=1; i<=n; ++i) {
			cout<<a[i]<<" ";
		}
		return 0;
	}
	return 0;
}

正解

考虑把2,3全部转化成1。

$mul_i$ 表示 $i$ 对全局的贡献，$sum_i$ 表示 $i$ 的带权调用次数（加法要乘的系数）

然后这两个可以在拓扑序上转移。

求答案时，首先把每个 $a_i$ 乘上全部的乘积，然后对于每个 1 类函数，加到序列上，需要乘 $sum$。

#include<bits/stdc++.h>
#define R(x) x=read()
#define int long long
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e-'0');
		e=getchar();
	}
	return x*y;
}
const int N=100005,mod=998244353;
int n,m,Q,a[N],f[N],ans;
struct node {
	int mul,sum,opt,pos,val;
} fun[N];
vector<int>G[N];
int ind[N],ord[N],tot;
queue<int>q;
void topo() {
	for(int i=1; i<=m; ++i) {
		if(!ind[i])q.push(i);
	}
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		ord[++tot]=u;
		for(auto v:G[u]) {
			if(!(--ind[v]))q.push(v);
		}
	}
}

void get_mul() {
	for(int i=m; i>=1; --i) {
		int u=ord[i];
		for(auto v:G[u]) {
			fun[u].mul=fun[u].mul*fun[v].mul%mod;
		}
	}
}

void get_sum() {
	for(int i=1; i<=m; ++i) {
		int u=ord[i],nw=1;
		for(int j=G[u].size()-1;j>=0;--j) {
			int v=G[u][j];
			fun[v].sum=(fun[v].sum+fun[u].sum*nw%mod)%mod;
			nw=nw*fun[v].mul%mod;
		}
	}
}
signed main() {
	R(n);
	for(int i=1; i<=n; ++i) {
		R(a[i]);
	}
	R(m);
	for(int i=1; i<=m; ++i) {
		R(fun[i].opt);
		fun[i].mul=1;
		if(fun[i].opt==1) {
			R(fun[i].pos),R(fun[i].val);
		} else if(fun[i].opt==2) {
			R(fun[i].val);
			fun[i].mul=fun[i].val;
		} else {
			int R(c);
			while(c--) {
				int R(x);
				G[i].push_back(x),++ind[x];
			}
		}
	}

	topo();
	get_mul();
	R(Q);
	for(int i=1; i<=Q; ++i)R(f[i]);
	int nw=1;
	for(int i=Q; i>=1; --i) {
		int x=f[i];
		fun[x].sum=(fun[x].sum+nw)%mod;
		nw=nw*fun[x].mul%mod;
	}
	get_sum();
	for(int i=1; i<=n; ++i) {
		a[i]=a[i]*nw%mod;
	}
	for(int i=1; i<=m; ++i) {
		if(fun[i].opt==1) {
			a[fun[i].pos]=(a[fun[i].pos]+fun[i].val*fun[i].sum%mod)%mod;
		}
	}
	for(int i=1; i<=n; ++i) {
		cout<<a[i]<<" ";
	}
	return 0;
}