当前位置：首页 > news >正文

I. 对线

news 2025/8/3 4:06:44

https://codeforces.com/gym/103186/problem/I

一开始感觉操作挺复杂的

但是写过Chino的数列 - 洛谷发现可以通过矩阵来实现swap操作，就想能不能用线段树维护矩阵来写

有三排兵线，我们维护区间和，因此初始矩阵就有了 $\begin{bmatrix} val1 &val2 &val3 &len \end{bmatrix}$

接下来分析每个操作的转移矩阵 (可以通过关系式推导或者随意设置一个转移矩阵，计算后看是否满足关系式)

op=1 $\begin{bmatrix} 1 &0 &0 &0 \\ 0& 1 &0 &0 \\ 0& 0 & 1& 0\\ v& v & v & 1 \end{bmatrix}$ ,区间加那一排在排下面赋值v

op=2 $\begin{bmatrix} 1 &0 &0 &0 \\ 0& 1 &0 &0 \\ 0& 0 & 1& 0\\ 0& 0 & 0 & 1 \end{bmatrix}$ 在这个矩阵的基础下，swap(1,2)有 $\begin{bmatrix} 0&1 &0 &0 \\ 1& 0 &0 &0 \\ 0& 0 & 1& 0\\ 0& 0 & 0 & 1 \end{bmatrix}$

op=3 $\begin{bmatrix} 1 &0 &0 &0 \\ 0& 1 &0 &0 \\ 0& 0 & 1& 0\\ 0& 0 & 0 & 1 \end{bmatrix}$ 在这个矩阵的基础下，1要得到3的分身有 $\begin{bmatrix} 1 &0 &0 &0 \\ 0& 1 &0 &0 \\ 1& 0 & 1& 0\\ 0& 0 & 0 & 1 \end{bmatrix}$

也就是 $val1=val1+val3$ ，也就是说这个操作可以累加的，因此不是给矩阵这个位置赋值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)#include<iostream>
using namespace std;
typedef long long ll;
const int N=3e5+9;
const int mod=998244353;
namespace Lan {inline string sread() {string s=" ";char e=getchar();while(e==' '||e=='\n')e=getchar();while(e!=' '&&e!='\n')s+=e,e=getchar();return s;}inline void swrite(string s){for(char e:s)putchar(e);printf("\n");}inline ll read() {ll x=0,y=1;char c=getchar();while(!isdigit(c)){if(c=='-')y=-1;c=getchar();}while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*=y;}inline void write(ll x) {if(x<0){x=-x,putchar('-');}ll sta[35],top=0;do sta[top++]=x%10,x/=10;while(x);while(top)putchar(sta[--top]+'0');}
}using namespace Lan;
int l=4;//长度
int vis[N<<2];
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 i=1;i<=l;i++){for(int j=1;j<=l;j++){m[i][j]=0;}}}void reset(){//设置成单位矩阵for(int i=1;i<=l;i++){for(int j=1;j<=l;j++){m[i][j]=(i==j);}}}Matrix friend operator * (const Matrix &a,const Matrix &b){//重载*Matrix ans;ans.clear();for(int k=1;k<=l;k++){for(int j=1;j<=l;j++){for(int i=1;i<=l;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 i=1;i<=l;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[N<<2];#define tl(id) id<<1#define tr(id) id<<1|1#define li inline#define pushup(id) seg[id].val=seg[tl(id)].val+seg[tr(id)].valli int inrange(int L,int R,int l,int r){return L>=l && R<=r;}li int outofrange(int L,int R,int l,int r){return L>r || l>R;}li void build(int id,int l,int r){seg[id].tag.reset();vis[id]=0;if(l==r){seg[id].val.m[1][4]=(r-l+1);return;}int mid=(l+r)>>1;build(tl(id),l,mid);build(tr(id),mid+1,r);pushup(id);}li void maketag(int id,int l,int r,Matrix x){seg[id].val=seg[id].val*x;seg[id].tag=seg[id].tag*x;vis[id]=1;}li void pushdown(int id,int l,int r){if(!vis[id]){return;}int mid=(l+r)>>1;maketag(tl(id),l,mid,seg[id].tag);maketag(tr(id),mid+1,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=(L+R)>>1;pushdown(id,L,R);return query(tl(id),L,mid,l,r)+query(tr(id),mid+1,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=(L+R)>>1;pushdown(id,L,R);modify(tl(id),L,mid,l,r,x);modify(tr(id),mid+1,R,l,r,x);pushup(id);}}
}tr;
#define node SEG::node
int main(){int n,q;n=read(),q=read();LIN.clear();Cell.reset();  	tr.build(1,1,n);for(int i=1;i<=q;i++){int op;op=read();if(op==0){int x,l,r;x=read(),l=read(),r=read();cout<<tr.query(1,1,n,l,r).m[1][x]%mod<<'\n';}else if(op==1){int x,l,r,y;x=read(),l=read(),r=read(),y=read();T.reset();T.m[4][x]=y;tr.modify(1,1,n,l,r,T);}else if(op==2){int x,y,l,r;x=read(),y=read(),l=read(),r=read();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;x=read(),y=read(),l=read(),r=read();T.reset();T.m[x][y]++;tr.modify(1,1,n,l,r,T);}}return 0;
}

勉强卡过，结构体比较美观()