WA 0 球条
查看原帖
WA 0 球条
504093
dyc2022楼主2024/8/17 15:25

rt,样例能过,代码 3.7k 相当清晰(

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 250006
#define MOD 998244353
using namespace std;
namespace IO
{
    int read()
    {
        int ret=0,bas=1;char ch=getchar();
        while(!isdigit(ch)&&ch!='-')ch=getchar();
        if(ch=='-')bas=-1,ch=getchar();
        while(isdigit(ch))ret=(ret<<3)+(ret<<1)+(ch^48),ch=getchar();
        return bas*ret;
    }
    void write(int k)
    {
        if(!k)return;
        write(k/10);
        putchar(k%10^48);
    }
    void print(int k)
    {
        if(k==0)putchar('0');
        else if(k<0)putchar('-'),write(-k);
        else write(k);
    }
}
using namespace IO;
struct Matrix{int num[6][6];}tree[N<<2],tag[N<<2],b0,b1,b2,b3;
int n,m;
int a[N],b[N],c[N];
Matrix operator +(Matrix x,Matrix y)
{
	Matrix ret;
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)ret.num[i][j]=(x.num[i][j]+y.num[i][j])%MOD;
	return ret;
}
Matrix operator *(Matrix x,Matrix y)
{
	Matrix ret;
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)ret.num[i][j]=0;
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)
			for(int k=1;k<=4;k++)
				ret.num[i][j]+=x.num[i][k]*y.num[k][j]%MOD,ret.num[i][j]%=MOD;
	return ret;
}
bool operator ==(Matrix x,Matrix y)
{
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)
			if(x.num[i][j]!=y.num[i][j])return 0;
	return 1;
}
Matrix base0()
{
	Matrix ret;
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)ret.num[i][j]=0;
	for(int i=1;i<=4;i++)ret.num[i][i]=1;
	return ret;
}
Matrix base1()
{
	Matrix ret=b0;
	ret.num[2][1]=1;
	return ret;
}
Matrix base2()
{
	Matrix ret=b0;
	ret.num[3][2]=1;
	return ret;
}
Matrix base3()
{
	Matrix ret=b0;
	ret.num[1][3]=1;
	return ret;
}
Matrix base4(int v)
{
	Matrix ret=b0;
	ret.num[4][1]=v;
	return ret;
}
Matrix base5(int v)
{
	Matrix ret=b0;
	ret.num[2][2]=v;
	return ret;
}
Matrix base6(int v)
{
	Matrix ret=b0;
	ret.num[3][3]=0,ret.num[4][3]=v;
	return ret;
}
void init(){b0=base0(),b1=base1(),b2=base2(),b3=base3();}
void push_up(int p){tree[p]=tree[p<<1]+tree[p<<1|1];}
void build(int p,int l,int r)
{
	tag[p]=b0;
	if(l==r)
	{
		for(int i=1;i<=4;i++)
			for(int j=1;j<=4;j++)tree[p].num[i][j]=0;
		tree[p].num[1][1]=a[l];
		tree[p].num[1][2]=b[l];
		tree[p].num[1][3]=c[l];
		tree[p].num[1][4]=1;
		return;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	push_up(p);
}
void addtag(int p,Matrix x){tree[p]=tree[p]*x,tag[p]=tag[p]*x;}
void push_down(int p)
{
	if(tag[p]==b0);
	else
	{
		addtag(p<<1,tag[p]);
		addtag(p<<1|1,tag[p]);
		tag[p]=b0;
	}
}
void update(int p,int l,int r,int L,int R,Matrix x)
{
	if(L>R)return;
	if(L<=l&&r<=R){addtag(p,x);return;}
	push_down(p);
	int mid=l+r>>1;
	if(L<=mid)update(p<<1,l,mid,L,R,x);
	if(R>mid)update(p<<1|1,mid+1,r,L,R,x);
	push_up(p);
}
Matrix query(int p,int l,int r,int L,int R)
{
	if(L<=l&&r<=R)return tree[p];
	push_down(p);
	int mid=l+r>>1;
	if(R<=mid)return query(p<<1,l,mid,L,R);
	if(L>mid)return query(p<<1|1,mid+1,r,L,R);
	return query(p<<1,l,mid,L,R)+query(p<<1|1,mid+1,r,L,R);
}
main()
{
	init();
	n=read();
	for(int i=1;i<=n;i++)a[i]=read(),b[i]=read(),c[i]=read();
	build(1,1,n);
	m=read();
	while(m--)
	{
		int opt=read(),l=read(),r=read(),x;
		if(opt==1)update(1,1,n,l,r,b1);
		else if(opt==2)update(1,1,n,l,r,b2);
		else if(opt==3)update(1,1,n,l,r,b3);
		else if(opt==4)x=read(),update(1,1,n,l,r,base4(x));
		else if(opt==5)x=read(),update(1,1,n,l,r,base5(x));
		else if(opt==6)x=read(),update(1,1,n,l,r,base6(x));
		else
		{
			Matrix ans=query(1,1,n,l,r);
			print(ans.num[1][1]),putchar(' ');
			print(ans.num[1][2]),putchar(' ');
			print(ans.num[1][2]),putchar('\n');
		}
	}
	return 0;
}
2024/8/17 15:25
加载中...