CSP-J/S 2020 题解

考完后花了大概两天时间把除了 tg T4 以外的所有题全部都做出来了，其实老实说，没有什么不会的算法或是数据结构（~~包括 T4？~~），但思维难度确实还是有一点大，像我这种平时不怎么练思维，光会写一些数据结构模板题或是刷水题的蒟蒻还是很难拿到高分的，还有就是一些细节很多，没注意到就很容易凉凉，所以总体来说虽然 tg 把两天改成了一天，但确实还是有区分度的~~把我这种菜鸡区分出来了~~，pj 还是可以，题目难度可能比去年稍稍难一点，但也不算很难，还是在意料之中。

题面

PJ

pj 主要是 T3 难想一点，然后 T4 是个 DP（~~居然没有图论！？~~），其他两个题就比较常规了，T1 还是 sb 签到题，T2 暴力的话很好写，但必须考虑优化，跟去年 T2 一样。

T1 优秀的拆分

签到题，首先看到若干个不同的 $2$ 的正整数次幂之和可以很快想到跟位运算有关，看完题面之后果然没错。

由于必须要是正整数次幂，那就代表 $n$ 的二进制下的第 $0$ 位不能为 $1$ ，也就是说只要是奇数就输出 $-1$ ，否则就一位一位找，如果某一位为 $1$ ，就拿个东西记录一下，最后倒序输出即可。

我考试的时候用的是 lowbit，如果不会的话请左转这篇文章。

#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
using namespace std;
int n,k,ans[100];
int main()
{
	scanf("%d",&n);
	if(n&1)
		printf("-1");
	else
	{
		for(;n;n-=lowbit(n))
			ans[++k]=lowbit(n);
		for(int i=k;i>=1;i--)
			printf("%d ",ans[i]);
	}
	return 0;
}

T2 直播获奖

一个简单的求第 K 大值的问题，方法很多，比较常见的是用个桶来记录每种成绩的数量，然后从后往前找第 K 个就好了，但时间复杂度为 $O(600n)$ （好吧这个表述可能有一点点问题，但这个常数是真的不能忽略啊喂）， $10^5$ 的数据有可能会被卡。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,w,a[N],num[1010];
int main()
{
	scanf("%d%d",&n,&w);
	for(int i=1;i<=n;i++)
	{
		int t=max(1,i*w/100);
		scanf("%d",&a[i]);
		num[a[i]]++;
		for(int j=600,k=0;j>=0;j--)
			if(k+num[j]>=t)
			{
				printf("%d ",j);
				break;
			}
			else
				k+=num[j];
	}
	return 0;
}

我们还有另外的方法来做这道题，考虑一个暴力算法，即每次对序列进行排序，然后输出第 K 项，我们发现插入排序可以很好地对序列进行维护，但美中不足的是它的单次复杂度还是 $O(n)$ ，这是个大问题，所以，我们可以尝试用一个 vector 来实现类似的功能，每次用 lower_bound 找到应该插入的位置，然后直接 insert 进去，我在考场上用的就是这个方法。

#include<bits/stdc++.h>
using namespace std;
int n,w;
vector<int> num;
int main()
{
	scanf("%d%d",&n,&w);
	for(int i=1;i<=n;i++)
	{
		int t=max(1,i*w/100)-1,a;
		scanf("%d",&a);
		num.insert(lower_bound(num.begin(),num.end(),a),a);
		printf("%d ",num[num.size()-1-t]);
	}
	return 0;
}

但老实说这种方法的复杂度很玄学，因为据一些大佬所说，insert 的时间复杂度并不是我在考试时以为的 $O(1)$ ，而是 $O(n)$ ，但由于常数极小，所以可以近似地看成 $O(\log n)$ （这里可能有误，欢迎各位大佬指正），另外，由于这道题数据规模还不是很大，所以没有被卡。

事实上，这道题存在一个 $O(n\log n)$ 的做法~~不是我在考试时的那种玄学操作~~，即用一个对顶堆维护第 K 大值。

对顶堆的原理比较有趣，我们用两个堆，一个是小根堆，一个是大根堆，这道题要求维护的是第 K 大值，对于每一个新插入的数 $x$ ，我们进行如下操作：

将 $x$ 与小根堆堆顶元素 $y$ 比较，如果 $x$ 大于 $y$ ，则把 $x$ 塞进小根堆里，反之，则把 $x$ 塞进大根堆里。
若小根堆里的数的数量小于 K，则把大根堆堆顶元素塞进小根堆里，并弹出，如此反复，直到小根堆里的数的数量等于 K。
若小根堆里的数的数量大于 K，则把小根堆堆顶元素塞进大根堆里，并弹出，如此反复，直到小根堆里的数的数量等于 K。
此时小根堆堆顶元素即为答案。

这个过程还是比较好想的，就像是把这个数列分成了两段，其中一段包含了最大的 K 个数，另外一段包含了其余的，当发现前一段的数的数量小于 K 时，就把后一段里最大的数划给前一段，反之则把前一段里最小的数划给后一段。

#include<bits/stdc++.h>
using namespace std;
int n,w,a;
priority_queue<int> p;
priority_queue< int,vector<int>,greater<int> > q;
int main()
{
    scanf("%d%d",&n,&w);
    for(int i=1;i<=n;i++)
    {
        int t=max(1,i*w/100);
        scanf("%d",&a);
        if(q.empty()||a>q.top())
            q.push(a);
        else
            p.push(a);
        while(q.size()<t)
        {
            q.push(p.top());
            p.pop();
        }
        while(q.size()>t)
        {
            p.push(q.top());
            q.pop();
        }
        printf("%d ",q.top());
    }
    return 0;
}

当然你要是实在闲着没事干的话平衡树也能很好地解决这道题，就是码量较上面这三种写法可能大了不少，不过时间复杂度也是比较优秀的 $O(n\log n)$ 。

T3 表达式

这道题是一道字符串的模拟题，要求求一个后缀逻辑表达式的值，后缀表达式的求解就不赘述了，可以参考 OI Wiki，这里主要讲一下如何快速求出反转变量的值后表达式的值。

首先，由于这是一个逻辑表达式，所以其值只有可能为 $0$ 或 $1$ ，换句话说，如果我们知道它的值不为 $0$ ，那它就一定为 $1$ ，这对里面的每一个变量都同样适用。

其次，每个变量都只出现一次，所以即使反转某个变量的值，也不可能出现某个运算符两边的值同时反转的情况。

最后，询问之间相互独立，也就是说我们每一次只用考虑一个变量的值的改变即可。

有这几点之后，结论就比较清晰了，我们可以预处理出哪些变量的值反转后会影响到整个表达式的值（这里我将其称为“关键的变量”），如果某次询问反转的是一个关键的变量的值，那么整个表达式的值一定会被反转。

接下来我们考虑如何求出这些变量，可以分两种情况讨论。

与运算符（ $x_1\land x2$ $x_{1} \land x 2$ ）
- 如果 $x_1$ 和 $x_2$ 都为 $1$ ，则这个表达式的值为 $1$ ，此时不管反转哪个变量的值，表达式的值都会变成 $0$ ，所以 $x_1$ 和 $x_2$ 都是关键的。
- 如果 $x_1$ 和 $x_2$ 只有一个为 $1$ ，则这个表达式的值为 $0$ ，此时如果把为 $0$ 的那个变量的值反转，表达式的值就会变成 $1$ ，所以为 $0$ 的那个变量是关键的，而如果为 $1$ 的那个变量反转，表达式的值还是 $0$ ，所以为 $1$ 的那个变量不是关键的。
- 如果 $x_1$ 和 $x_2$ 都为 $0$ ，则不管反转哪个，表达式的值都为 $0$ ，所以它们都不是关键的。
或运算符（ $x_1\lor x_2$ $x_{1} \lor x_{2}$ ）
- 如果 $x_1$ 和 $x_2$ 都为 $0$ ，则这个表达式的值为 $0$ ，此时不管反转哪个变量的值，表达式的值都会变成 $1$ ，所以 $x_1$ 和 $x_2$ 都是关键的。
- 如果 $x_1$ 和 $x_2$ 只有一个为 $0$ ，则这个表达式的值为 $1$ ，此时如果把为 $1$ 的那个变量的值反转，表达式的值就会变成 $0$ ，所以为 $1$ 的那个变量是关键的，而如果为 $0$ 的那个变量反转，表达式的值还是 $1$ ，所以为 $0$ 的那个变量不是关键的。
- 如果 $x_1$ 和 $x_2$ 都为 $1$ ，则不管反转哪个，表达式的值都为 $1$ ，所以它们都不是关键的。

（至于取反运算符（ $\lnot x$ ）可以忽略，因为它是单目运算符，我们甚至可以直接把它取反的那个变量的值取反，然后删掉它，当然我个人不推荐这样，因为会多出许多代码）

容易发现，上述规则不仅适用于单个变量，也同样适用于表达式，即 $x_1$ 和 $x_2$ 可以是表达式，我们对这两个表达式分别求出它的关键的变量之后，在运算时按照上述规则进行判断，如果某个表达式是关键的，则它的所有关键的变量都是这个新表达式的关键的变量，反之则都不是，这样不停地对表达式进行合并，最后就能求出整个表达式的关键的变量和表达式的值，将其存在数组里排个序，在询问时 lower_bound 一下，判断反转的变量是否是关键的，如果是，就输出表达式值反转后的值，如果不是，直接输出原值即可，时间复杂度 $O(|s|+q\log n)$ 。

（看到很多大佬是对表达式建了棵树，然后打标记，可以做到 $O(|s|)$ ，然而我太弱了，考场上只想出来用栈来做，所以只好借助了 STL 的力量，而且时间复杂度比较**，常数也是能上天的那种，在 lg 上跑了整整 1.77s，所以强烈建议看完本篇题解后再看一下 lg 上的题解）

STL 操作较多，主要是用了很多 assign 和 insert，如果有疑问，请自行百度。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
string s;
int n,q,len,tid,ans,x[N],p[N];
stack<int> num;
stack< vector<int> > val;
vector<int> k;
void solve()
{
	for(int i=0;i<len;i++)
	{
		if(s[i]==' ')
		{
			if(tid)
			{
				num.push(x[tid]);
				vector<int> tmp;
				tmp.push_back(tid);
				val.push(tmp);
			}
			tid=0;
		}
		else
		{
			if(s[i]=='x')
				tid=0;
			if(s[i]>='0'&&s[i]<='9')
				tid=tid*10+s[i]-'0';
			if(s[i]=='|')
			{
				int x1=num.top();
				num.pop();
				int x2=num.top();
				num.pop();
				num.push(x1|x2);
				vector<int> t1,t2,empty;
				t1.assign(val.top().begin(),val.top().end());
				val.pop();
				t2.assign(val.top().begin(),val.top().end());
				val.pop();
				if(!x1&&!x2)
					t1.insert(t1.end(),t2.begin(),t2.end());
				if(!x1&&x2)
					swap(t1,t2);
				if(!x1||!x2)
					val.push(t1);
				else
					val.push(empty);
			}
			if(s[i]=='&')
			{
				int x1=num.top();
				num.pop();
				int x2=num.top();
				num.pop();
				num.push(x1&x2);
				vector<int> t1,t2,empty;
				t1.assign(val.top().begin(),val.top().end());
				val.pop();
				t2.assign(val.top().begin(),val.top().end());
				val.pop();
				if(x1&&x2)
					t1.insert(t1.end(),t2.begin(),t2.end());
				if(x1&&!x2)
					swap(t1,t2);
				if(x1||x2)
					val.push(t1);
				else
					val.push(empty);
			}
			if(s[i]=='!')
			{
				int x1=num.top();
				num.pop();
				num.push(!x1);
			}
		}
	}
	ans=num.top();
	k.assign(val.top().begin(),val.top().end());
}
int main()
{
	getline(cin,s);
	len=s.size();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&x[i]);
	solve();
	sort(k.begin(),k.end());
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		int j;
		scanf("%d",&j);
		int t=lower_bound(k.begin(),k.end(),j)-k.begin();
		if(t<k.size()&&k[t]==j)
			printf("%d\n",ans^1);
		else
			printf("%d\n",ans);
	}
	return 0;
}

~~能想到用栈来存 vector 的恐怕也只有我了~~

T4 方格取数

从数据规模~~和题目名称~~可以看出来应该是一道 DP，可以用 $dp_{i,j}$ 表示走到第 $i$ 行 $j$ 列所能取到的最大的数字和，但由于这道题有可能从下面走到上面来，所以不能用传统的转移方式。

注意到这道题不能从右边走到左边，这启发我们一列一列地进行递推，具体来说，我们可以发现，从 $(x-1,y_1)$ 走到 $(x,y_2)$ ，一定是先走到 $(x,y_1)$ ，再一路向上或向下走到 $(x,y_2)$ ，并收集从 $(x,y_1)$ 到 $(x,y_2)$ 的所有数字，因此，应该可以想到如下递推式

$dp_{i,j}=\max_{1\le k\le n} dp_{k,j-1}+\begin{cases}\sum_{x=i}^k a_{x,j-1}(i\le k)\\\sum_{x=k}^i a_{x,j-1}(i>k)\end{cases}$

但如果对于每一个 $dp_{i,j}$ 都枚举一遍这个最大值的话，那么时间复杂度为 $O(n^2m)$ ，很明显不行，考虑优化。

可以发现，对于同一列的 $dp_{i,j}$ ，这个枚举的过程会有很多重复的运算，我们可以用一个 $mx$ 变量记录 $dp_{i-1,j}$ 所取到的最大的值，在此基础上得出 $dp_{i,j}$ 应取的最大值，先考虑第二种，即 $i>k$ 的情况，为了便于理解，这里放一张图片，阐述 $dp_{i,j}$ 的得出过程。

如图，这是已经求出的一个 $dp_{i-1,j}$ ，而 $dp_{i,j}$ 的来源有两种。

可以看出，如果我们从 $(k,j-1)$ 走到 $(k,j)$ 是走到 $(k,j)$ 的最优方案，那么可以一直往下，中间不停地把方格里的值累加到 $mx$ 里，直到遇到一个地方 $(i,j)$ ，使得 $dp_{k,j-1}+\sum_{x=k}^i a_{x,j}<dp_{i,j-1}+a_{i,j}$ ，就说明这个地方从上一列走过来会更优，那我们就可以更新 $mx$ 变量的值为 $dp_{i,j-1}+a_{i,j}$ ，并重复上述过程，而对于 $i\le k$ 的情况也是一样的思路。

还有一点需要注意的地方，因为第 $1$ 列不存在从上一列走过来的情况，我们需要进行预处理。

还有什么不明白的就看代码吧，个人感觉码风还是不错的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e3+10;
ll n,m,mx,a[N][N],dp[N][N];
int main()
{
	memset(dp,-0x3f,sizeof(dp));//初始化最小值
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%lld",&a[i][j]);
	dp[0][1]=0;
	for(int i=1;i<=n;i++)
		dp[i][1]=a[i][1]+dp[i-1][1];//预处理第一列
	for(int j=2;j<=m;j++)
	{
		mx=dp[1][j-1];
		for(int i=1;i<=n;i++)//先统计 i>=k 的情况
		{
			mx=max(dp[i][j-1],mx)+a[i][j];//用一个变量不断累加，遇到更优的情况就更新之
			dp[i][j]=max(dp[i][j],mx);
		}
		mx=dp[n][j-1];
		for(int i=n;i>=1;i--)//再统计 i<=k 的情况
		{
			mx=max(dp[i][j-1],mx)+a[i][j];//同上
			dp[i][j]=max(dp[i][j],mx);
		}
	}
	printf("%lld",dp[n][m]);
	return 0;
}

DP 不是我最擅长的东西~~准确来说是我最不擅长的东西~~，所以考试时并没有做对这道题，只得了 30pts，不过还好前三题都对了，应该是有 1= 了。

TG

这次的提高真的是让我感觉心态爆炸，尤其是 T1T2，T1 就不用说了，恶心大模拟，数据也难算，调试也很**，整体来说很没有体验，T2 犯了一个超级 sb 的错误，导致挂了 35pts，T3T4 还算正常发挥，主要是前两题出错太多，最后只有 150pts，1= 很悬。

T1 儒略日

~~在开始这道题的题解之前请允许我问候出题人全家。~~

简单来说，这道题就是让你求从公元前 4713 年 1 月 1 日往后数 $r$ 天是哪一天，但有几个细节。

从公元前 4713 年 1 月 1 日到公元 1582 年 10 月 4 日这段时间里没有现在百年不闰的说法，只要年份是 $4$ 的倍数就是闰年。
公元 1582 年 10 月 4 日的下一天是公元 1582 年 10 月 15 日。
公元 0 年不存在，即公元前 1 年的下一年是公元 1 年，所以对于公元前年份来说，年份模 $4$ 余 $1$ 的才是闰年。
其他的和现在的历法一样。

一个很简单的方法是用这个天数不停地减去这一年的天数，然后把年份数加一，如果天数小于等于这一年的天数了，就再让它不停的减去这一年的每个月份的天数，直到它小于等于这一月的天数。

然而，CCF 给我们的数据范围是

年份答案不超过 $10^9$

况且还有多组数据，所以很明显这个方法行不通，考虑优化。

相信大家都做过这道题，它的思路是用取模来代替周期性的模拟，我们也可以依葫芦画瓢。

具体来说，我们分三段来考虑。

公元前 4713 年 1 月 1 日到公元 1582 年 10 月 4 日，这一段四年一闰，即四年一个周期。
公元 1582 年 10 月 15 日到公元 1582 年 12 月 31 日，这一段由于不是整年份，又有间隔的天数，所以我们分开特判。
公元 1583 年 1 月 1 日到~~公元 inf 年 12 月 31 日~~以后，这一段四年一闰，百年不闰，四百年再闰，即每四百年为一个周期。

具体的就不详细说了，~~也没什么好说的了~~，还是看代码吧。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll q,n,mon[20]={0,31,28,31,30,31,30,31,31,30,31,30,31};
ll check_year_special(ll x)//带 _special 的就是用来判断 1582 年以前的年份或月份的
{
	if(x<0)
		if((-x)%4==1)
			return 366;
		else
			return 365;
	else
		if(x%4==0)
			return 366;
		else
			return 365;
}
ll check_month_special(ll x,ll y)
{
	if(check_year_special(x)==366&&y==2)
		return 29;
	else
		return mon[y];
}
ll check_year(ll x)
{
	if(x%400==0||(x%4==0&&x%100!=0))
		return 366;
	else
		return 365;
}
ll check_month(ll x,ll y)
{
	if(check_year(x)==366&&y==2)
		return 29;
	else
		return mon[y];
}
int main()
{
	scanf("%lld",&q);
	while(q--)
	{
		scanf("%lld",&n);
		if(n<=2299160)//从公元前 4713 年 1 月 1 日到公元 1582 年 10 月 4 日的天数
		{
			ll y=n/1461*4-4713,m=1,flag=0;//1461 为四年的天数
			n%=1461;
			if(y>=0)
			{
				flag=1;//特判是否过了公元前 1 年
				y++;
			}
			while(n>=check_year_special(y))//一年一年地减
			{
				n-=check_year_special(y++);
				if(y==0)
				{
					flag=1;
					y++;
				}
			}
			while(n>=check_month_special(y,m))//一月一月地减
				n-=check_month_special(y,m++);
			if(flag)
				printf("%lld %lld %lld\n",n+1,m,y);
			else
				printf("%lld %lld %lld BC\n",n+1,m,-y);
		}
		if(2299160<n)
		{
			n-=2299161;//减去之前的天数，重新开始计算
			if(n<=16)//特判 1582 年 10 月 15 日到 1582 年 12 月 31 日
				printf("%lld 10 1582\n",n+15);
			if(16<n&&n<=46)
				printf("%lld 11 1582\n",n-16);
			if(46<n&&n<=77)
				printf("%lld 12 1582\n",n-46);
			if(77<n)
			{
				n-=78;
				ll y=1583+n/146097*400,m=1;//146097 为每四百年的天数
				n%=146097;
				while(n>=check_year(y))
					n-=check_year(y++);
				while(n>=check_month(y,m))
					n-=check_month(y,m++);
				printf("%lld %lld %lld\n",n+1,m,y);
			}
		}
	}
	return 0;
}

没什么复杂的算法，但需要非常注意细节，同时数学也要好~~计算器也要用的好~~，否则是真的难调，我在考场上调了一个半小时都没整对，最后还是爆零。。。

T2 动物园

这道题个人感觉比 T1 简单多了，不过位运算的特性是真的难受，两三处小小的错误直接就丢了 35pts，真的难受。。。

对于这道题，我们可以先根据饲养的动物和要求算出清单，再根据清单反过来算一遍这些动物编号的哪些二进制位可以为 $1$ ，假设有 $x$ 位可以为 $1$ ，那就一共可以饲养 $2^x$ 种动物，因为我们可以把中间不能为 $1$ 的那些位扣掉，剩下来的就是一个每一位都为 $1$ 的共有 $x$ 位的二进制数，其中每一位都可以为 $0$ 或者为 $1$ ，所以总的方案数就是 $2^x$ ，再从其中扣掉已经饲养的 $n$ 种动物，就是还能饲养的动物数。

另外，这道题有很多注意点，下面列举一下（可能不全，欢迎补充）。

这道题 $k\le 64$ ，超出了 long long 的范围，必须要用 unsigned long long，如果你不会拼 unsigned，请找你的英语老师。（40pts）
由于位运算的神奇特性，1<<x会被默认为 int 类型，即如果 $x$ 大于等于 $31$ ，即使你是将这个值赋给一个 unsigned long long 类型的值，它还是会在运算时自然溢出，解决方法是使用1ull<<x。（40pts）（~~这就是我在考试时犯的傻逼错误，少打了两个 ull~~）
根据数据范围， $x$ 有可能为 $64$ ，如果 $n$ 此时为 $0$ ，那么答案就是 $2^{64}$ ，超出了 unsigned long long 的范围，需要特判，另外，虽然 CCF 的数据没有卡，但个人认为最好是特判一下 $x=64$ 的情况，毕竟这样虽然最后会减一个 $n$ ，但在运算过程中也会溢出。（5pts）
如果你用的是 scanf（用 cin 貌似会超时？），记住 unsigned long long 的格式控制符是 %ull，不是 %llu（没有这种格式控制符），也不是 %uld（也没有这种格式控制符）。（100pts）

~~我很好奇有多少人挂在了第 $4$ 点。~~

#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
using namespace std;
typedef unsigned long long ll;//unsigned！！！
const ll N=1e6+10;
ll cnt(ll x)
{
	ll sum=0;
	for(;x;x-=lowbit(x))
		sum++;
	return sum;
}
ll n,m,c,k,mk,ans,a[N],p[N],q[N];
bitset<100000010> lt;//我用的 bitset 存清单QwQ
int main()
{
	scanf("%llu%llu%llu%llu",&n,&m,&c,&k);
	for(ll i=1;i<=n;i++)
	{
		scanf("%llu",&a[i]);
		mk|=a[i];
	}
	for(ll i=1;i<=m;i++)
	{
		scanf("%llu%llu",&p[i],&q[i]);
		if(mk&(1ull<<p[i]))
			lt[q[i]]=1;
	}
	for(ll i=1;i<=m;i++)
		if(!lt[q[i]]&&!(ans&(1ull<<p[i])))
			ans^=(1ull<<p[i]);
	ll tot=k-cnt(ans);
	if(tot==64)
		if(n==0)
			printf("18446744073709551616");//特判
		else
			printf("%llu",18446744073709551616-n);//特判*2
	else
		printf("%llu",(1ull<<tot)-n);
	return 0;
}

T3 函数调用

这道题乍一看很像数据结构题，但实际上并不是，而是一道有点思维难度的拓扑排序。

可以发现，这道题实质上可以看成是把所有数乘上一个值 $x$ ，然后再把某些数加上一些值（好好理解一下），举个例子， $(a+3)*4=a*4+12$ 。但这样暴力模拟的话肯定会超时（~~事实上由于 CCF 的数据十分之水，所以暴力可以拿到 70pts~~）。

考虑计算每个函数的贡献，可以发现， $x$ 是非常容易求出来的，我们只需要根据函数之间的调用关系，一边 DFS，一边累计所有 $2$ 号函数所乘的值就行了，然后我们需要想办法快速算出那些需要加上的值。因为每一个 $1$ 号函数都是单点增加，所以比较容易想到的办法是求出每一个 $1$ 号函数执行的次数，最后统一增加，这个执行次数不单单指它被调用的次数，还要把它每次被调用之后乘的值也累加进去，比如如果一个 $3$ 号函数的作用相当于先把第一个数加上 $3$ ，再把所有数乘上 $4$ ，那么第一个被调用的函数就相当于调用了 $4$ 次，这个也是我们需要计算的。

先假设只有一个 $3$ 号函数，它的作用如下：

把第一个数加 $1$ 。
把所有数乘上 $2$ 。
把第三个数加上 $2$ 。
把第四个数加上 $100$ 。
把所有数乘上 $10$ 。

那么不难看出，我们相当于是把 $5$ 执行了 $1$ 遍， $2$ ， $3$ 和 $4$ 执行了 $10$ 遍， $1$ 执行了 $20$ 遍，也就是说，我们可以从后往前遍历每一个 $3$ 号函数，用一个临时变量 $t$ 累计乘了多少，每调用一个函数，就把它的执行次数加上 $t$ ，并让 $t$ 乘上这个函数所要乘的数（如果没有要乘的数就默认为 $1$ ），慢慢累加就行了。

但这只是一个 $3$ 号函数的情况，实际上整个函数调用过程可能会很复杂，这时候我们又该怎么办呢？

由于题面中说了，不会出现递归，也就是说如果我们把函数调用的过程画成一张图，它实际上是一个 DAG，比如样例二画成一张图的话就是下面这个样子。

因此，我们可以考虑进行拓扑排序，在一开始输入时，对于每一个 $3$ 号函数，把它们抽象成图中的一个点，向它们所调用的那些函数连一条有向边，然后预处理出每个函数所要乘的值 $mul_i$ （包括它调用的那些函数，如上图中的 $3$ 乘的数就是 $5,6,7,8$ 所要乘的数的积），可以跑一遍 DFS 解决。在排序过程中，我们不停地累加某个函数的执行次数，对于每一个被函数 $i$ 调用的函数 $j$ ，它所增加的执行次数为 $f_i\times t$ （ $f_i$ 是函数 $i$ 被调用的次数， $t$ 就是上面提到的那个临时变量），然后再把 $t$ 乘上 $mul_j$ ，需要注意，正如上文所说，这个过程必须反向遍历所有边，也就是说，如果一开始的调用顺序为 $4\ 3\ 5\ 2\ 3$ ，那么遍历顺序就为 $3\ 2\ 5\ 3\ 4$ 。

对了，有一个技巧，可以把最后的那个执行序列也看成是一个 $3$ 号函数，作为 $0$ 号点建边，DFS 的时候直接从 $0$ 开始就行了。

然后就没什么了，记得不停地取模就行了，还有什么不明白的就看代码吧。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10,mod=998244353;
ll n,m,q,mul[N],vis[N],a[N],in[N],f[N],fun[N][2];
vector<int> edge[N];
ll dfs(int u)
{
	if(vis[u])
		return mul[u];
	vis[u]=1;
	for(int i=0;i<edge[u].size();i++)
	{
		int v=edge[u][i];
		mul[u]=mul[u]*dfs(v)%mod;
	}
	return mul[u];
}
void topo()
{
	queue<int> q;
	for(int i=0;i<=m;i++)
		if(!in[i])
			q.push(i);
	while(q.size())
	{
		int u=q.front();
		q.pop();
		ll rec=1;
		for(int i=edge[u].size()-1;i>=0;i--)
		{
			int v=edge[u][i];
			f[v]=(f[v]+f[u]*rec%mod)%mod;
			rec=rec*mul[v]%mod;
			in[v]--;
			if(!in[v])
				q.push(v);
		}
	}
}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	scanf("%lld",&m);
	for(int i=1;i<=m;i++)
	{
		mul[i]=1;
		ll op,p,v,c;
		int g;
		scanf("%lld",&op);
		if(op==1)
			scanf("%lld%lld",&fun[i][0],&fun[i][1]);
		if(op==2)
			scanf("%lld",&mul[i]);
		if(op==3)
		{
			scanf("%lld",&c);
			for(int j=1;j<=c;j++)
			{
				scanf("%d",&g);
				edge[i].push_back(g);
				in[g]++;
			}
		}
	}
	scanf("%lld",&q);
	for(int i=1;i<=q;i++)
	{
		int func;
		scanf("%d",&func);
		edge[0].push_back(func);
		in[func]++;
	}
	f[0]=mul[0]=1;
	dfs(0);
	topo();
	for(int i=1;i<=n;i++)
		a[i]=a[i]*mul[0]%mod;
	for(int i=1;i<=m;i++)
		if(fun[i][0])
			a[fun[i][0]]=(a[fun[i][0]]+f[i]*fun[i][1]%mod)%mod;
	for(int i=1;i<=n;i++)
		printf("%lld ",a[i]);
	return 0;
}