大魔法使い

一、テーマ
これを問題とする
二、解法
線分木のマークの問題だとわかりやすいですが、マークの順番が気持ち悪いです.
簡単な解法があります.すべての修正操作をマトリクス乗算と見なし、タグもマトリクスで維持し、私たちの値は4です.× 1 4\times1 4×1のマトリクスメンテナンス(A A Aを値、B B Bを操作マトリクスとし、B× A B\times A B×A更新値):A B C l e nbegin{matrix}A\B\Clenend{ matrix}ABClenその後操作はそれぞれ以下のマトリクスでメンテナンス(操作番号1−6−6−6 1−6−6の順):1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0&0 0&0 0&0&1&0 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 1begin{matrix}1&0&0&0\\0&1&1&0\\0&0&1&0\\0&0&0&1\end{matrix} 1000​0100​0110​0001​ 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1\begin{matrix}1&0&0&0\\0&1&0&0\\1&0&1&0\\0&0&0&1\end{matrix} 1010​0100​0010​0001​ 1 0 0 v 0 1 0 0 0 0 1 0 0 0 0 1\begin{matrix}1&0&0&v\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{matrix}0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1 1 0 0 0 0 0 0 0 0 0 0 0 0&end{ matrix}1000 0 0 0 0 v 1の最後の問題はタグ順序であり、行列は直接乗算で重ねることができるので、私の上の構造方法に従って、新しく加えた行列をA A Aとして、すでにマークした行列はB B Bで、それでは保存した行列はAであるべきです× B A\times B A×B(本質的に式行列乗算には交換則がない).この問題にはカードが必要です.詳しくはコードを参照してください.

#pragma GCC optimize(2)
#include 
#include 
const int M = 250005;
const int MOD = 998244353;
int read()
{
    int x=0,flag=1;
    char c;
    while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
    while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*flag;
}
int n,m,op,l,r,v;
struct Matrix
{
    int n,m,a[5][5];
    Matrix()
    {
        n=m=0;
        memset(a,0,sizeof a);
    }
    void reset()
    {
        for(int i=1; i<=4; i++) for(int j=1; j<=4; j++) a[i][j]=(i==j);
    }
    void clear()
    {
        memset(a,0,sizeof a);
    }
    Matrix operator * (const Matrix &B) const
    {
        Matrix R;
        R.n=n;
        R.m=B.m;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
            {
                if(a[i][j]==0) continue;
                for(int k=1; k<=B.m; k++)
                    R.a[i][k]=(R.a[i][k]+1ll*a[i][j]*B.a[j][k])%MOD;
            }
        return R;
    }
    Matrix operator + (const Matrix &B) const
    {
        Matrix R;
        R.n=n;
        R.m=m;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                R.a[i][j]=(a[i][j]+B.a[i][j])%MOD;
        return R;
    }
} A,emp;
struct node
{
    Matrix val,la;
    node()
    {
        val.m=1;
        val.n=la.n=la.m=4;
        la.reset();
    }
} tr[M*4];
void build(int i,int l,int r)
{
    if(l==r)
    {
        tr[i].val.a[1][1]=read();
        tr[i].val.a[2][1]=read();
        tr[i].val.a[3][1]=read();
        tr[i].val.a[4][1]=1;
        return ;
    }
    int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    tr[i].val=tr[i<<1].val+tr[i<<1|1].val;
}
void down(int i)
{
    int ls=i<<1,rs=i<<1|1;
    tr[ls].val=tr[i].la*tr[ls].val;
    tr[rs].val=tr[i].la*tr[rs].val;
    tr[ls].la=tr[i].la*tr[ls].la;
    tr[rs].la=tr[i].la*tr[rs].la;
    tr[i].la.reset();
}
void updata(int i,int l,int r,int L,int R)
{
    if(l>R || L>r) return ;
    if(L<=l && r<=R)
    {
        tr[i].la=A*tr[i].la;
        tr[i].val=A*tr[i].val;
        return ;
    }
    int mid=(l+r)>>1;
    down(i);
    updata(i<<1,l,mid,L,R);
    updata(i<<1|1,mid+1,r,L,R);
    tr[i].val=tr[i<<1].val+tr[i<<1|1].val;
}
Matrix query(int i,int l,int r,int L,int R)
{
    if(l>R || L>r) return emp;
    if(L<=l && r<=R) return tr[i].val;
    int mid=(l+r)>>1;
    down(i);
    return query(i<<1,l,mid,L,R)+query(i<<1|1,mid+1,r,L,R);
}
signed main()
{
    A.n=A.m=emp.n=4;
    emp.m=1;
    n=read();
    build(1,1,n);
    m=read();
    for(int i=1; i<=m; i++)
    {
        op=read();
        l=read();
        r=read();
        A.reset();
        if(op==1)
            A.a[1][2]=1;
        if(op==2)
            A.a[2][3]=1;
        if(op==3)
            A.a[3][1]=1;
        if(op==4)
            A.a[1][4]=v=read();
        if(op==5)
            A.a[2][2]=v=read();
        if(op==6)
            A.a[3][3]=0,A.a[3][4]=v=read();
        if(op!=7)
            updata(1,1,n,l,r);
        if(op==7)
        {
            Matrix t=query(1,1,n,l,r);
            printf("%d %d %d
",t.a[1][1],t.a[2][1],t.a[3][1]);
        }
    }
}