[LOJ - 2980]「THUSCH 2017」大魔法师

线段树+矩阵乘法（毒瘤题 ）

LOJ - 2980

题意简述

给你$n$个三元组，表示为$(A_i,B_i,C_i)$ ；$m$次操作，每次选择一段区间，对于区间内的元素$\quad \forall i \in [l,r]$，有一下7种操作

1. 令$A_i=A_i+B_i$
2. 令$B_i=B_i+C_i$
3. 令$C_i=C_i+A_i$
4. 令$A_i=A_i+v$ ($v$为每次给的值，下同)
5. 令$B_i=B_i*v$
6. 令$C_i=v$
7. 分别求出$\sum_{i=l}^r A_i$ , $\sum_{i=l}^r B_i$ 和 $\sum_{i=l}^r C_i$

$1\le n,m \le 2.5\times 10^5$

真是一波毒瘤操作。

思路&题解

首先看到区间动态问题，肯定会想到线段树。然而每个点有三种元素，又涉及各种毒瘤操作，显然朴素修改不太方便，于是我们考虑用矩阵乘法来表示。

$$(A_i,B_i,C_i)\iff \begin{bmatrix} A_i \\ B_i \\ C_i \\ 1 \end{bmatrix}$$

转化三元组为矩阵，多加一个1是方便 (4) ~ (5) 的操作，很容易写出如下的转移矩阵。

$$\begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} A_i \\ B_i \\ C_i \\ 1 \end{bmatrix} = \begin{bmatrix} A_i +B_i\\ B_i \\ C_i \\ 1 \end{bmatrix} \tag{op=1}$$

$$\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} A_i \\ B_i \\ C_i \\ 1 \end{bmatrix} = \begin{bmatrix} A_i \\ B_i +C_i\\ C_i \\ 1 \end{bmatrix} \tag{op=2}$$

$$\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} A_i \\ B_i \\ C_i \\ 1 \end{bmatrix} = \begin{bmatrix} A_i \\ B_i \\ C_i +A_i\\ 1 \end{bmatrix} \tag{op=3}$$

$$\begin{bmatrix} 1 & 0 & 0 & v \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} A_i \\ B_i \\ C_i \\ 1 \end{bmatrix} = \begin{bmatrix} A_i +v\\ B_i \\ C_i \\ 1 \end{bmatrix} \tag{op=4}$$

$$\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & v & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} A_i \\ B_i \\ C_i \\ 1 \end{bmatrix} = \begin{bmatrix} A_i \\ B_i \times v\\ C_i \\ 1 \end{bmatrix} \tag{op=5}$$

$$\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & v \\ 0 & 0 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} A_i \\ B_i \\ C_i \\ 1 \end{bmatrix} = \begin{bmatrix} A_i \\ B_i \\ v \\ 1 \end{bmatrix} \tag{op=6}$$

挺好理解的吧，手模一遍就能明白了。
操作7就是把$l,r$之间的矩阵统统加起来，输出$A,B,C$即可。

然后就可以欢快得用线段树维护了，线段树每个节点维护一个矩阵，表示当前区间每个点的矩阵之和。 因为矩乘满足结合律：$(A+B)\times C=A\times C+B\times C$ 故可以对一段区间的矩阵之和进行操作，剩下的与普通线段树基本无异，不再赘述。

细节

众所周知，矩阵乘法常数大，还要带一个线段树。。。
建议手写矩阵，别用vector。

CODE

本人又臭又长的代码

#pragma GCC optimize(2)
#include <cstdio>
#include <cstring>
#include <vector>
#define fi first
#define se second
#define re register
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef pair<int,int> pi;
const int N = 250010;
const ll mod = 998244353ll;
struct mar { //手写矩阵
    ll v[4][4];
    int n;
    mar() {}
    mar(int _n,int _val) {
        n=_n;
        memset(v,_val,sizeof(v));
    }
    mar(int _n,vec in) {
        n=_n;
        for(re int i=0;i<n;++i)
            for(re int j=0;j<n;++j)
                v[i][j]=in[i*n+j];
    }
    inline ll* operator[](int p) {
        return v[p];
    }
    inline mar operator*(const mar b)const {
        mar c=mar(n,0);
        for(re int k=0;k<n;++k)
            for(re int i=0;i<n;++i)
                for(re int j=0;j<n;++j)
                    c.v[i][j]=(c.v[i][j]+v[i][k]*b.v[k][j])%mod;
        return c;
    }
    inline mar operator+(const mar b)const {
        mar c=mar(n,0);
        for(re int i=0;i<n;++i)
            for(re int j=0;j<n;++j)
                c.v[i][j]=(v[i][j]+b.v[i][j])%mod;
        return c;
    }
    inline bool operator==(const mar b) const {
        if(n!=b.n) return 0;
        for(re int i=0;i<n;++i)
            for(re int j=0;j<n;++j)
                if(v[i][j]!=b.v[i][j]) return 0;
        return 1;
    }
    inline bool operator!=(const mar b) const {
        return !((*this)==b);
    }
};
const mar e=mar(4,vec{1,0,0,0, 0,1,0,0, 0,0,1,0, 0,0,0,1});
const mar opt[7]={ //转移矩阵打表
    mar(),
    mar(4,vec{1,1,0,0, 0,1,0,0, 0,0,1,0, 0,0,0,1}),
    mar(4,vec{1,0,0,0, 0,1,1,0, 0,0,1,0, 0,0,0,1}),
    mar(4,vec{1,0,0,0, 0,1,0,0, 1,0,1,0, 0,0,0,1}),
    mar(4,vec{1,0,0,0, 0,1,0,0,    0,0,1,0, 0,0,0,1}),
    mar(4,vec{1,0,0,0, 0,0,0,0, 0,0,1,0, 0,0,0,1}),
    mar(4,vec{1,0,0,0, 0,1,0,0, 0,0,0,0, 0,0,0,1})
};
const pi optps[7]={pi(0,0),pi(0,0),pi(0,0),pi(0,0),pi(0,3),pi(1,1),pi(2,3)};
mar tr[N<<2],tag[N<<2];
int n,m;
inline int red() {
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='0') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
mar getT(int op,int v=1) {
    mar T=opt[op];
    T[optps[op].fi][optps[op].se]=v;
    return T;
}
void print(mar A) {
    printf("%lld %lld %lld\n",A[0][0],A[1][0],A[2][0]);
}
void pushup(int x) {
    tr[x]=tr[x<<1]+tr[x<<1|1];
}
void pushdown(int x) {
    if(tag[x]!=e) {
        tr[x<<1]=tag[x]*tr[x<<1];
        tr[x<<1|1]=tag[x]*tr[x<<1|1];
        tag[x<<1]=tag[x]*tag[x<<1];
        tag[x<<1|1]=tag[x]*tag[x<<1|1];
        tag[x]=e;
    }
}
void build(int l=1,int r=n,int x=1) {
    tag[x]=e;
    if(l==r) {
        tr[x]=mar(4,0);
        tr[x][0][0]=red();
        tr[x][1][0]=red();
        tr[x][2][0]=red();
        tr[x][3][0]=1LL;
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,x<<1);
    build(mid+1,r,x<<1|1);
    pushup(x);
}
mar query(int L,int R,int l=1,int r=n,int x=1) {
    if(L<=l&&r<=R) {
        return tr[x];
    }
    int mid=(l+r)>>1;
    mar ret=mar(4,0);
    pushdown(x);
    if(L<=mid) ret=ret+query(L,R,l,mid,x<<1);
    if(R>mid) ret=ret+query(L,R,mid+1,r,x<<1|1);
    return ret;    
}
void modify(int L,int R,mar T,int l=1,int r=n,int x=1) {
    if(L<=l&&r<=R) {
        tr[x]=T*tr[x];
        tag[x]=T*tag[x];
        return ;
    }
    int mid=(l+r)>>1;
    pushdown(x);
    if(L<=mid) modify(L,R,T,l,mid,x<<1);
    if(R>mid) modify(L,R,T,mid+1,r,x<<1|1);
    pushup(x);
}
// 常数巨大无比，吸氧卡过QAQ
int main() {
    n=red();
    build();
    m=red();
    while(m--) {
        int op,x,y,v;
        op=red(),x=red(),y=red();
        if(op==7) {
            print(query(x,y));
        }else {
            if(op>=4) {
                v=red();
                modify(x,y,getT(op,v));
            }
            else modify(x,y,getT(op));
        }
    }
    return 0;
}