社区讨论

求助秒为什么RE

P7077[CSP-S 2020] 函数调用参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@locxy8ak
此快照首次捕获于
2023/10/30 21:34
2 年前
此快照最后确认于
2023/11/05 07:56
2 年前
查看原帖
打的暴力,把数组开到1e6就多了20pts,不应该1e5就好了吗
CPP
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;

const int mod=998244353,N=1e5+5;
int n,m,q,f,tot;
int a[N],T[N],p[N],v[N],c[N];
vector<int>g[N];
struct node{
	int l,r,val,mul;
}t[N<<2];

void build(int u,int l,int r)
{
	t[u].l=l,t[u].r=r,t[u].mul=1;
	if(l==r) return t[u].val=a[l],void();
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r); 
}

void update(int u,int x,int c)
{
	if(t[u].mul!=1)
	{
		t[u<<1].mul=1ll*t[u].mul*t[u<<1].mul%mod;
		t[u<<1|1].mul=1ll*t[u].mul*t[u<<1|1].mul%mod;
		t[u<<1].val=1ll*t[u].mul*t[u<<1].val%mod;
		t[u<<1|1].val=1ll*t[u].mul*t[u<<1|1].val%mod;
		t[u].mul=1;
	}
	if(t[u].l==t[u].r) return t[u].val=(t[u].val+c)%mod,void();
	int mid=t[u].l+t[u].r>>1;
	if(x<=mid) update(u<<1,x,c);
	else update(u<<1|1,x,c);
}

void pushdown(int u)
{
	if(t[u].mul!=1)
	{
		t[u<<1].mul=1ll*t[u].mul*t[u<<1].mul%mod;
		t[u<<1|1].mul=1ll*t[u].mul*t[u<<1|1].mul%mod;
		t[u<<1].val=1ll*t[u].mul*t[u<<1].val%mod;
		t[u<<1|1].val=1ll*t[u].mul*t[u<<1|1].val%mod;
		t[u].mul=1;
	}
	if(t[u].l==t[u].r) return printf("%d ",t[u].val),void();
	pushdown(u<<1),pushdown(u<<1|1);
}

void solve(int x)
{
	for(register int i=0;i<c[x];++i)
		if(T[g[x][i]]==1) update(1,p[g[x][i]],v[g[x][i]]);
		else if(T[g[x][i]]==2) t[1].mul=1ll*t[1].mul*v[g[x][i]]%mod;
		else solve(g[x][i]);
}

int main(void)
{
	//freopen("call.in","r",stdin);
	//freopen("call.out","w",stdout);
	scanf("%d",&n);
	for(register int i=1;i<=n;++i)
		scanf("%d",a+i);
	build(1,1,n);
	scanf("%d",&m);
	for(register int i=1;i<=m;++i)
	{
		scanf("%d",T+i);
		if(T[i]==1) scanf("%d%d",p+i,v+i);
		else if(T[i]==2) scanf("%d",v+i);
		else
		{
			scanf("%d",c+i);
			g[i].resize(c[i]);
			for(register int j=0;j<c[i];++j)
				scanf("%d",&g[i][j]);
		}
	}
	scanf("%d",&q);
	while(q--)
	{
		scanf("%d",&f);
		if(T[f]==1) update(1,p[f],v[f]);
		else if(T[f]==2) t[1].mul=1ll*t[1].mul*v[f]%mod;
		else solve(f);
	}
	pushdown(1);
	return 0;
}


回复

1 条回复,欢迎继续交流。

正在加载回复...