WA35pts求救
查看原帖
WA35pts求救
568521
I_AM_CIMOTA楼主2023/8/10 20:03

不知道哪里出了问题

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=2.5e5+5,Mod=998244353;
const int M[3][4][4]={{{1,1,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1}}
,{{1,0,0,0},{0,1,1,0},{0,0,1,0},{0,0,0,1}}
,{{1,0,0,0},{0,1,0,0},{1,0,1,0},{0,0,0,1}}};
int n,m,opt,x,y,v;
struct node{int a,b,c,d;}p[N],s[N<<2],ans,cc;
struct matrix{
	int A[4][4];
	matrix operator * (const matrix& xx){
		matrix yy;
		for(int i=0;i<4;i++)
		for(int j=0;j<4;j++)
			yy.A[i][j]=0;
		for(int i=0;i<4;i++)
		for(int k=0;k<4;k++)
		for(int j=0;j<4;j++)
			(yy.A[i][j]+=(A[i][k]*xx.A[k][j])%Mod)%=Mod;
		return yy;
	}
}C,I,tag[N<<2];

void upd(int u){
	s[u].a=(((C.A[0][0]*s[u].a%Mod+C.A[0][1]*s[u].b%Mod)%Mod+C.A[0][2]*s[u].c%Mod)%Mod+C.A[0][3]*s[u].d%Mod)%Mod;
	s[u].b=(((C.A[1][0]*s[u].a%Mod+C.A[1][1]*s[u].b%Mod)%Mod+C.A[1][2]*s[u].c%Mod)%Mod+C.A[1][3]*s[u].d%Mod)%Mod;
	s[u].c=(((C.A[2][0]*s[u].a%Mod+C.A[2][1]*s[u].b%Mod)%Mod+C.A[2][2]*s[u].c%Mod)%Mod+C.A[2][3]*s[u].d%Mod)%Mod;
	s[u].d=(((C.A[3][0]*s[u].a%Mod+C.A[3][1]*s[u].b%Mod)%Mod+C.A[3][2]*s[u].c%Mod)%Mod+C.A[3][3]*s[u].d%Mod)%Mod;
	tag[u]=C*tag[u];
}
void upd1(int u){s[u].a=cc.a,s[u].b=cc.b,s[u].c=cc.c,s[u].d=cc.d;}
void query(int u){
	ans.a=(ans.a+s[u].a)%Mod;
	ans.b=(ans.b+s[u].b)%Mod;
	ans.c=(ans.c+s[u].c)%Mod;
	ans.d=(ans.d+s[u].d)%Mod;
}
void up(int u){
	s[u].a=(s[u<<1].a+s[u<<1|1].a)%Mod;
	s[u].b=(s[u<<1].b+s[u<<1|1].b)%Mod;
	s[u].c=(s[u<<1].c+s[u<<1|1].c)%Mod;
	s[u].d=(s[u<<1].d+s[u<<1|1].d)%Mod;
}
void down(int u){
	matrix tmp=C;
	C=tag[u];
	upd(u<<1);
	upd(u<<1|1);
	C=tmp;
	tag[u]=I;
}
void (*op)(int);

void build(int u,int l,int r){
	if(l==r){
		cc.a=p[l].a,cc.b=p[l].b,cc.c=p[l].c,cc.d=p[l].d;
		upd1(u);
		return;
	}
	int mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	up(u);
}

void dfs(int u,int l,int r){
	if(x<=l&&y>=r){op(u);return;}
	down(u);
	int mid=(l+r)>>1;
	if(x<=mid)dfs(u<<1,l,mid);
	if(y>mid)dfs(u<<1|1,mid+1,r);
	up(u);
}

signed main(){
	for(int i=0;i<4;i++)
	for(int j=0;j<4;j++)
		I.A[i][j]=(i==j);
	scanf("%lld",&n);
	for(int i=1;i<=(n<<2);i++)tag[i]=I;
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld",&p[i].a,&p[i].b,&p[i].c);
		p[i].d=1;
	}
	C=I;
	build(1,1,n);
	scanf("%lld",&m);
	while(m--){
		scanf("%lld%lld%lld",&opt,&x,&y);
		if(opt>=1&&opt<=3){
			for(int i=0;i<4;i++)
			for(int j=0;j<4;j++)
				C.A[i][j]=M[opt-1][i][j];
			op=upd;
			dfs(1,1,n);
		}
		else if(opt>=4&&opt<=6){
			scanf("%lld",&v);
			C=I;
			if(opt==4)C.A[0][3]=v;
			else if(opt==5)C.A[1][1]=v;
			else C.A[2][2]=0,C.A[2][3]=v;
			op=upd;
			dfs(1,1,n);
		}
		else{
			ans.a=0,ans.b=0,ans.c=0,ans.d=0,op=query;
			dfs(1,1,n);
			printf("%lld %lld %lld\n",ans.a,ans.b,ans.c);
		}
	}
	return 0;
}
2023/8/10 20:03
加载中...