「题解」「THUSCH2017」大魔法师

THUSCH2017 T4，用矩阵乘法描述修改操作的好题。

题目链接：LibreOJ 2980。

题目

THUSCH2017 T4。

题目描述

~~中二病患者~~ 大魔法师小 L 制作了 $n$ 个魔力水晶球，每个水晶球有水、火、土三个属性的能量值。小 L 把这 $n$ 个水晶球在地上从前向后排成一行，然后开始今天的魔法表演。

我们用 $A _ i,B _ i,C _ i$ 分别表示从前向后第 $i$ 个水晶球（下标从 $1$ 开始）的水、火、土的能量值。

小 L 计划施展 $m$ 次魔法。每次，他会选择一个区间 $[L,R]$，然后施展以下 $7$ 大类、种魔法之一：

魔力激发：令区间里每个水晶球中特定属性的能量爆发，从而使另一个特定属性的能量增强。具体来说，有以下三种可能的表现形式：
- 火元素激发水元素能量：令 $A _ i=A _ i+B _ i$。
- 土元素激发火元素能量：令 $B _ i=B _ i+C _ i$。
- 水元素激发土元素能量：令 $C _ i=C _ i+A _ i$。
- 需要注意的是，增强一种属性的能量并不会改变另一种属性的能量，例如并不会使增加或减少。
魔力增强：小 L 挥舞法杖，消耗自身 $v$ 点法力值，来改变区间里每个水晶球的特定属性的能量。具体来说，有以下三种可能的表现形式：
- 火元素能量定值增强：令 $A _ i=A _ i+v$。
- 水元素能量翻倍增强：令 $B _ i=B _ i\cdot v$。
- 土元素能量吸收融合：令 $C _ i=v$。
魔力释放：小 L 将区间里所有水晶球的能量聚集在一起，融合成一个新的水晶球，然后送给场外观众。生成的水晶球每种属性的能量值等于区间内所有水晶球对应能量值的代数和。需要注意的是，魔力释放的过程不会真正改变区间内水晶球的能量。

值得一提的是，小 L 制造和融合的水晶球的原材料都是定制版的 OI 工厂水晶，所以这些水晶球有一个能量阈值 $998244353$。当水晶球中某种属性的能量值大于等于这个阈值时，能量值会自动对阈值取模，从而避免水晶球爆炸。

小 W 为小 L（唯一的）观众，围观了整个表演，并且收到了小 L 在表演中融合的每个水晶球。小 W 想知道，这些水晶球蕴涵的三种属性的能量值分别是多少。

数据范围

$100\%$ 的数据，$n,m\leq 2.5\times 10^5$，$0\leq A _ i,B _ i,C _ i,v\leq 998244353$。

$10\%$ 的数据，$n\times m\leq 10^7$。
另外 $10\%$ 的数据，每次魔法的区间均为 $[1,n]$。
另外 $10\%$ 的数据，每次非询问魔法的影响区间均为 $[1,n]$，所有修改在询问之前。
另外 $10\%$ 的数据，$\text{opt}\in\{4,5,6,7\}$。
另外 $15\%$ 的数据，$\text{opt}\in\{1,2,7\}$。
另外 $15\%$ 的数据，$\text{opt}\in\{1,2,3,5,7\}$。
另外 $15\%$ 的数据，$n,m\leq 10^5$。
其他数据，无特殊约定。

提示：请注意本题的空间限制，妥善处理你的程序的内存消耗。

时空限制

题目编号	时间限制	空间限制
LibreOJ 2980	$5\text{s}$	$512\text{MiB}$

题解

思路

用矩阵乘法代替修改操作即可把所有修改操作转化为区间乘法，用线段树维护即可。下面列出各个操作的矩阵。

操作一

$$(a,b,c)\to(a+b,b,c)$$

$$
\begin{bmatrix}a&b&c&1\end{bmatrix}\times
\begin{bmatrix}
1&0&0&0\\
1&1&0&0\\
0&0&1&0\\
0&0&0&1
\end{bmatrix}
=\begin{bmatrix}a+b&b&c&1\end{bmatrix}
$$

操作二

$$(a,b,c)\to(a,b+c,c)$$

$$
\begin{bmatrix}a&b&c&1\end{bmatrix}\times
\begin{bmatrix}
1&0&0&0\\
0&1&0&0\\
0&1&1&0\\
0&0&0&1
\end{bmatrix}
=\begin{bmatrix}a&b+c&c&1\end{bmatrix}
$$

操作三

$$(a,b,c)\to(a,b,c+a)$$

$$
\begin{bmatrix}a&b&c&1\end{bmatrix}\times
\begin{bmatrix}
1&0&1&0\\
0&1&0&0\\
0&0&1&0\\
0&0&0&1
\end{bmatrix}
=\begin{bmatrix}a&b&c+a&1\end{bmatrix}
$$

操作四

$$(a,b,c)\to(a+v,b,c)$$

$$
\begin{bmatrix}a&b&c&1\end{bmatrix}\times
\begin{bmatrix}
1&0&0&0\\
0&1&0&0\\
0&0&1&0\\
v&0&0&1
\end{bmatrix}
=\begin{bmatrix}a+v&b&c&1\end{bmatrix}
$$

操作五

$$(a,b,c)\to(a,b\times v,c)$$

$$
\begin{bmatrix}a&b&c&1\end{bmatrix}\times
\begin{bmatrix}
1&0&0&0\\
0&v&0&0\\
0&0&1&0\\
0&0&0&1
\end{bmatrix}
=\begin{bmatrix}a&b\times v&c&1\end{bmatrix}
$$

操作六

$$(a,b,c)\to(a,b,v)$$

$$
\begin{bmatrix}a&b&c&1\end{bmatrix}\times
\begin{bmatrix}
1&0&0&0\\
0&1&0&0\\
0&0&0&0\\
0&0&v&1
\end{bmatrix}
=\begin{bmatrix}a&b&v&1\end{bmatrix}
$$

操作七

矩阵加法。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define MOD 998244353
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=2.5e5+5;
const int MAXM=2.5e5+5;

int n;

const int MAXSIZE=4;

struct Matrix{
    int unit[MAXSIZE][MAXSIZE];
    inline Matrix(void){
        memset(unit,0,sizeof(unit));
        return;
    }
    inline int* operator[](reg int i){
        return unit[i];
    }
    inline Matrix operator*(const Matrix& a){
        Matrix res;
        for(reg int i=0;i<MAXSIZE;++i)
            for(reg int j=0;j<MAXSIZE;++j)
                for(reg int k=0;k<MAXSIZE;++k)
                    res[i][j]=(res[i][j]+(ll)unit[i][k]*a.unit[k][j]%MOD)%MOD;
        return res;
    }
    inline Matrix operator+(const Matrix& a){
        Matrix res;
        for(reg int i=0;i<MAXSIZE;++i)
            for(reg int j=0;j<MAXSIZE;++j)
                res[i][j]=(unit[i][j]+a.unit[i][j])%MOD;
        return res;
    }
};

Matrix I;
int a[MAXN],b[MAXN],c[MAXN];

namespace SegmentTree{
    #define lson ( (k) << 1 )
    #define rson ( (k) << 1 | 1 )
    #define mid ( ( (l) + (r) ) >> 1 )
    bool istag[MAXN<<2];
    Matrix tag[MAXN<<2];
    Matrix val[MAXN<<2];
    inline void pushup(reg int k){
        val[k]=val[lson]+val[rson];
        return;
    }
    inline void Mul(reg int k,const Matrix& x){
        val[k]=val[k]*x;
        if(!istag[k]){
            istag[k]=true;
            tag[k]=x;
        }
        else
            tag[k]=tag[k]*x;
        return;
    }
    inline void pushdown(reg int k){
        if(istag[k]){
            Mul(lson,tag[k]);
            Mul(rson,tag[k]);
            istag[k]=false;
        }
        return;
    }
    inline void Build(reg int k,reg int l,reg int r){
        if(l==r){
            val[k][0][0]=a[l];
            val[k][0][1]=b[l];
            val[k][0][2]=c[l];
            val[k][0][3]=1;
            return;
        }
        Build(lson,l,mid);
        Build(rson,mid+1,r);
        pushup(k);
        return;
    }
    inline void Update(reg int k,reg int l,reg int r,reg int L,reg int R,const Matrix& x){
        if(L<=l&&r<=R){
            Mul(k,x);
            return;
        }
        pushdown(k);
        if(L<=mid)
            Update(lson,l,mid,L,R,x);
        if(R>mid)
            Update(rson,mid+1,r,L,R,x);
        pushup(k);
        return;
    }
    inline Matrix Query(reg int k,reg int l,reg int r,reg int L,reg int R){
        if(L<=l&&r<=R)
            return val[k];
        pushdown(k);
        Matrix res;
        if(L<=mid)
            res=res+Query(lson,l,mid,L,R);
        if(R>mid)
            res=res+Query(rson,mid+1,r,L,R);
        return res;
    }
    #undef lson
    #undef rson
    #undef mid
}

using namespace SegmentTree;

int main(void){
    n=read();
    I[0][0]=I[1][1]=I[2][2]=I[3][3]=1;
    for(reg int i=1;i<=n;++i)
        a[i]=read(),b[i]=read(),c[i]=read();
    Build(1,1,n);
    reg int m=read();
    while(m--){
        static int opt,l,r,v;
        static Matrix M;
        M=I;
        opt=read(),l=read(),r=read();
        switch(opt){
            case 1:{
                M[1][0]=1;
                Update(1,1,n,l,r,M);
                break;
            }
            case 2:{
                M[2][1]=1;
                Update(1,1,n,l,r,M);
                break;
            }
            case 3:{
                M[0][2]=1;
                Update(1,1,n,l,r,M);
                break;
            }
            case 4:{
                v=read();
                M[3][0]=v;
                Update(1,1,n,l,r,M);
                break;
            }
            case 5:{
                v=read();
                M[1][1]=v;
                Update(1,1,n,l,r,M);
                break;
            }
            case 6:{
                v=read();
                M[2][2]=0,M[3][2]=v;
                Update(1,1,n,l,r,M);
                break;
            }
            case 7:{
                Matrix res=Query(1,1,n,l,r);
                printf("%d %d %d\n",res[0][0],res[0][1],res[0][2]);
                break;
            }
            default:break;
        }
    }
    return 0;
}

友情链接

近期评论

「题解」「THUSCH2017」大魔法师

题目

题目描述

数据范围

时空限制

题解

思路

代码

You may also like...

发表评论取消回复

题目

题目描述

数据范围

时空限制

题解

思路

代码

You may also like...

「题解」最短距离

「题解」遥远的国度

「题解」「FZOI 周赛 #9 Div.0」翻卡片

发表评论 取消回复

发表评论取消回复