网站开发人员岗位要求,苏州口碑好的保洁公司,郑州企业网站建站,wordpress歌词插件https://codeforces.com/gym/103186/problem/I 一开始感觉操作挺复杂的
但是写过Chino的数列 - 洛谷 发现可以通过矩阵来实现swap操作#xff0c;就想能不能用线段树维护矩阵来写
有三排兵线#xff0c;我们维护区间和#xff0c;因此初始矩阵就有了
接下来分析每个操作的…https://codeforces.com/gym/103186/problem/I 一开始感觉操作挺复杂的
但是写过Chino的数列 - 洛谷 发现可以通过矩阵来实现swap操作就想能不能用线段树维护矩阵来写
有三排兵线我们维护区间和因此初始矩阵就有了
接下来分析每个操作的转移矩阵 (可以通过关系式推导或者随意设置一个转移矩阵计算后看是否满足关系式)
op1 ,区间加那一排在排下面赋值v
op2在这个矩阵的基础下swap(1,2)有
op3在这个矩阵的基础下1要得到3的分身有
也就是也就是说这个操作可以累加的因此不是给矩阵这个位置赋值1而是一次!
虽然12s,但是我还是要卡
建议不要写结构体加快读对矩阵乘法进行优化以及懒标记的下传判断优化
// Problem: I. 对线
// Contest: Codeforces - The 2021 Shanghai Collegiate Programming Contest
// URL: https://codeforces.com/gym/103186/problem/I
// Memory Limit: 1024 MB
// Time Limit: 12000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includeiostream
using namespace std;
typedef long long ll;
const int N3e59;
const int mod998244353;
namespace Lan {inline string sread() {string s ;char egetchar();while(e ||e\n)egetchar();while(e! e!\n)se,egetchar();return s;}inline void swrite(string s){for(char e:s)putchar(e);printf(\n);}inline ll read() {ll x0,y1;char cgetchar();while(!isdigit(c)){if(c-)y-1;cgetchar();}while(isdigit(c)){x(x3)(x1)(c^48);cgetchar();}return x*y;}inline void write(ll x) {if(x0){x-x,putchar(-);}ll sta[35],top0;do sta[top]x%10,x/10;while(x);while(top)putchar(sta[--top]0);}
}using namespace Lan;
int l4;//长度
int vis[N2];
int add(int a, int b){return (a b) % mod;}
int mul(int a, int b){return 1ll * a * b % mod;}
int sub(int a, int b){return ((a - b) % mod mod) % mod;}
struct Matrix{ int m[5][5];//最多1e2Matrix() : m{} {}//构造函数直接构造转移矩阵[5,5](0-5)void clear(){for(int i1;il;i){for(int j1;jl;j){m[i][j]0;}}}void reset(){//设置成单位矩阵for(int i1;il;i){for(int j1;jl;j){m[i][j](ij);}}}Matrix friend operator * (const Matrix a,const Matrix b){//重载*Matrix ans;ans.clear();for(int k1;kl;k){for(int j1;jl;j){for(int i1;il;i){//乘法操作if(!a.m[i][k] || !b.m[k][j]){continue;}ans.m[i][j]add(ans.m[i][j],mul(a.m[i][k]%mod,b.m[k][j]));}}}return ans;} Matrix friend operator (const Matrix A,const Matrix B){//重载Matrix Ans;Ans.clear();for(int i1;il;i){//l,转换矩阵大小Ans.m[1][i]add(Ans.m[1][i],A.m[1][i]);Ans.m[1][i]add(Ans.m[1][i],B.m[1][i]);}return Ans;}
}Tr,Cell,LIN,T;
struct SEG{struct node{int l,r;Matrix val;Matrix tag;}seg[N2];#define tl(id) id1#define tr(id) id1|1#define li inline#define pushup(id) seg[id].valseg[tl(id)].valseg[tr(id)].valli int inrange(int L,int R,int l,int r){return Ll Rr;}li int outofrange(int L,int R,int l,int r){return Lr || lR;}li void build(int id,int l,int r){seg[id].tag.reset();vis[id]0;if(lr){seg[id].val.m[1][4](r-l1);return;}int mid(lr)1;build(tl(id),l,mid);build(tr(id),mid1,r);pushup(id);}li void maketag(int id,int l,int r,Matrix x){seg[id].valseg[id].val*x;seg[id].tagseg[id].tag*x;vis[id]1;}li void pushdown(int id,int l,int r){if(!vis[id]){return;}int mid(lr)1;maketag(tl(id),l,mid,seg[id].tag);maketag(tr(id),mid1,r,seg[id].tag);seg[id].tag.reset();vis[id]0;}li Matrix query(int id,int L,int R,int l,int r){if(inrange(L,R,l,r)){return seg[id].val;}else if(!outofrange(L,R,l,r)){int mid(LR)1;pushdown(id,L,R);return query(tl(id),L,mid,l,r)query(tr(id),mid1,R,l,r);}else{return LIN;}}li void modify(int id,int L,int R,int l,int r,Matrix x){if(inrange(L,R,l,r)){maketag(id,L,R,x);}else if(!outofrange(L,R,l,r)){int mid(LR)1;pushdown(id,L,R);modify(tl(id),L,mid,l,r,x);modify(tr(id),mid1,R,l,r,x);pushup(id);}}
}tr;
#define node SEG::node
int main(){int n,q;nread(),qread();LIN.clear();Cell.reset(); tr.build(1,1,n);for(int i1;iq;i){int op;opread();if(op0){int x,l,r;xread(),lread(),rread();couttr.query(1,1,n,l,r).m[1][x]%mod\n;}else if(op1){int x,l,r,y;xread(),lread(),rread(),yread();T.reset();T.m[4][x]y;tr.modify(1,1,n,l,r,T);}else if(op2){int x,y,l,r;xread(),yread(),lread(),rread();T.reset();swap(T.m[y][x],T.m[x][x]); swap(T.m[x][y],T.m[y][y]);tr.modify(1,1,n,l,r,T); }else{int x,y,l,r;xread(),yread(),lread(),rread();T.reset();T.m[x][y];tr.modify(1,1,n,l,r,T);}}return 0;
}
勉强卡过结构体比较美观()
