前言
此题属于周末 狂欢 自闭赛系列
题目
讲解
首先这明显是一道数据结构题：线段树
但是我们怎么维护呢？我们有整整六个操作！！！而且操作彼此之间还有顺序问题，这导致我们的懒标记并不好搞
我们 自己想 通过老师的讲解：使用矩阵！！！
这样所有的问题都迎刃而解了
线段树的每个节点使用(1 imes 4)的矩阵，(4 imes 4)的懒标记
转移很好想
想不出来看代码
另外，这道题 轻微 卡常
代码
//12252024832524
#pragma GCC optimize(2)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 250005;
const int MOD = 998244353;
int n;
int Read()
{
int x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
void Put1(int x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
void Put(int x)
{
if(x < 0) putchar('-'),x = -x;
Put1(x);
}
template <typename T>T Max(T x,T y){return x > y ? x : y;}
template <typename T>T Min(T x,T y){return x < y ? x : y;}
template <typename T>T Abs(T x){return x < 0 ? -x : x;}
int Add(int x)
{
if(x >= MOD) return x - MOD;
return x;
}
struct Matrix
{
int n,m,a[5][5];
Matrix(){for(int i = 1;i <= 4;++ i) for(int j = 1;j <= 4;++ j) a[i][j] = 0;}
void put()
{
for(register int i = 1;i <= n;++ i)
{
for(register int j = 1;j < m;++ j)
{
Put(a[i][j]);
putchar(' ');
}
Put(a[i][m]);
putchar('
');
}
}
Matrix operator + (const Matrix &C)//临时加法
{
Matrix r;
r.n = n;
r.m = m;
for(register int j = 1;j <= m;++ j)
r.a[1][j] = Add(a[1][j] + C.a[1][j]);
return r;
}
Matrix operator * (const Matrix &C)
{
Matrix r;
r.n = n;
r.m = C.m;
for(register int i = 1;i <= r.n;++ i)
for(register int k = 1;k <= m;++ k)
if(a[i][k])
for(register int j = 1;j <= r.m;++ j)
r.a[i][j] = Add(1ll * a[i][k] * C.a[k][j] % MOD + r.a[i][j]);
return r;
}
}im,optm[7],nt;//单位矩阵,操作的矩阵,空矩阵
struct SegmentTree
{
struct node
{
int l,r;
Matrix mat,lazy;
}a[950019];
void up(const int x)
{
a[x].mat = a[x<<1].mat + a[x<<1|1].mat;
}
void down(const int x)
{
a[x<<1].mat = a[x<<1].mat * a[x].lazy;
a[x<<1|1].mat = a[x<<1|1].mat * a[x].lazy;
a[x<<1].lazy = a[x<<1].lazy * a[x].lazy;
a[x<<1|1].lazy = a[x<<1|1].lazy * a[x].lazy;
a[x].lazy = im;
}
void build(const int x,const int l,const int r)
{
a[x].l = l;
a[x].r = r;
a[x].mat.n = 1;
a[x].mat.m = 4;
a[x].mat.a[1][4] = r-l+1;
a[x].lazy = im;
if(l == r)
{
a[x].mat.a[1][1] = Read();//Ai
a[x].mat.a[1][2] = Read();//Bi
a[x].mat.a[1][3] = Read();//Ci
return ;
}
int mid = (l+r) >> 1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
up(x);
}
void update(const int x,const int l,const int r,Matrix val)
{
if(a[x].l > r || a[x].r < l) return;
if(l <= a[x].l && a[x].r <= r)
{
a[x].mat = a[x].mat * val;
a[x].lazy = a[x].lazy * val;
return ;
}
down(x);
update(x<<1,l,r,val);
update(x<<1|1,l,r,val);
up(x);
}
Matrix query(const int x,const int l,const int r)
{
if(a[x].l > r || a[x].r < l) return nt;
if(l <= a[x].l && a[x].r <= r) return a[x].mat;
down(x);
return query(x<<1,l,r) + query(x<<1|1,l,r);
}
}t;
void pre()
{
im.n = im.m = nt.m = 4;
nt.n = 1;
for(register int i = 1;i <= 4;++ i) im.a[i][i] = 1;
for(register int i = 1;i <= 6;++ i) optm[i] = im;
optm[1].a[2][1] = 1;//1. Ai += Bi
optm[2].a[3][2] = 1;//2. Bi += Ci
optm[3].a[1][3] = 1;//3. Ci += Ai
optm[6].a[3][3] = 0;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
pre();
n = Read();
t.build(1,1,n);
for(register int Q = Read(); Q ;-- Q)
{
int opt = Read(),l = Read(),r = Read();
if(opt <= 3) t.update(1,l,r,optm[opt]);
else if(opt <= 6)
{
int v = Read();
if(opt == 4) optm[4].a[4][1] = v;//4. Ai += v
else if(opt == 5) optm[5].a[2][2] = v;//5. Bi *= v
else optm[6].a[4][3] = v;//6. Ci = v
t.update(1,l,r,optm[opt]);
}
else
{
Matrix val = t.query(1,l,r);
val.m = 3;
val.put();
}
}
return 0;
}
卡常卡吐了
我以后码矩阵一定从(sout0)开始