Wannafly Winter Camp Day8(Div1,onsite) E题 Souls-like Game 线段树矩阵乘法

（有任何问题欢迎留言或私聊 && 欢迎交流讨论哦

Catalog

Catalog
- Problem：传送门
Solution：
- AC_Code：
- Problem Description：

Problem：传送门

Portal

原题目描述在最下面。

简单的说，每个点是一个矩阵，区间赋值和区间求积。

Solution：

\(div2\)版本就\(O(n*m*9)\)暴力更新暴力矩阵乘法求答案就行了，代码挺短的，有需要的话去另一篇博客里有代码。

\(div1\)题解就上面这个，相信大家看完应该都能\(ac\)。

本题只有两种操作，区间赋值和区间求和(矩阵的积)。很自然就想到要用线段树优化咯，然后线段树每个节点都是一个矩阵。

但是这题要先把区间长度扩展为2的幂次，为什么呢？因为：

长度为\(n\)的区间长度有大概\(log(n)\)种，但是当\(n\)不是\(2\)的幂次的时候，各种区间的长度是没有规律的。

这题线段树每个节点维护的是矩阵信息，用\(lazy\)标记优化区间赋值时，其实就是求矩阵的\(k\)次幂。

因为会有很多区间的长度相同，可以先把矩阵的k次幂预处理出来。

而只有当总长度是2的幂次时，每个节点覆盖的区间长度都会是2的幂次。这样就解释完了。

理解了这个，这题就随便写了。

AC_Code：

//哇，这题ac完感觉好爽啊

//第一次写这种结构体线段树还重载操作符的，海星

//没有人写博客，只能看着官方题解意会解法

#include<bits/stdc++.h>

#define clr(a, b) memset(a,b,sizeof((a)))

#define lson rt<<1

#define rson rt<<1|1

using namespace std;

typedef long long LL;

const int MXN = 2e5 + 7;

const LL mod = 998244353;

int n, m, Q;

int ar[MXN][3][3], two[33];

int lazy[MXN<<2][3][3], flag[MXN<<2];

map<int, int> mp;

struct edge {

    int opt, l, r;

    int ar[3][3];

}node[MXN];

struct lp {

    int sum[3][3];

    friend lp operator *(const lp&a, const lp&b) {

        lp c;

        clr(c.sum, 0);

        for(int k = 0; k < 3; ++k) for(int i = 0; i < 3; ++i) for(int j = 0; j < 3; ++j) {

            c.sum[i][j] = (c.sum[i][j]+(LL)a.sum[i][k]*b.sum[k][j])%mod;

        }

        return c;

    }

}cw[MXN<<2], tp[MXN][33];

void push_up(int rt) {

    cw[rt] = cw[lson] * cw[rson];

}

void build(int l,int r,int rt) {

    flag[rt] = -1;

    if(l == r) {

        for(int i = 0; i < 3; ++i) for(int j = 0; j < 3; ++j) cw[rt].sum[i][j] = ar[l][i][j];

        return ;

    }

    int mid = (l + r) >> 1;

    build(l, mid, lson); build(mid+1,r,rson);

    push_up(rt);

}

void push_down(int l,int mid,int r,int rt) {

    if(flag[rt] == -1) return;

    flag[lson] = flag[rson] = flag[rt];

    for(int i = 0; i < 3; ++i) for(int j = 0; j < 3; ++j) lazy[lson][i][j] = lazy[rt][i][j], lazy[rson][i][j] = lazy[rt][i][j];

    cw[lson] = tp[flag[rt]][mp[mid-l+1]-1];

    cw[rson] = tp[flag[rt]][mp[r-mid]-1];

    assert(mp[mid-l+1]); assert(mp[r-mid]);

    flag[rt] = -1;

}

void update(int L,int R,int id,int l,int r,int rt) {

    if(L <= l && r <= R) {

        flag[rt] = id;

        for(int i = 0; i < 3; ++i) for(int j = 0; j < 3; ++j) lazy[rt][i][j] = node[id].ar[i][j];

        assert(mp[r-l+1]);

        cw[rt] = tp[id][mp[r-l+1]-1];

        return ;

    }

    int mid = (l + r) >> 1;

    push_down(l, mid, r, rt);

    if(L > mid) update(L, R, id, mid+1, r, rson);

    else if(R <= mid) update(L, R, id, l, mid, lson);

    else {

        update(L,mid,id,l,mid,lson); update(mid+1,R,id,mid+1,r,rson);

    }

    push_up(rt);

}

lp query(int L,int R,int l,int r,int rt) {

    if(L <= l && r <= R) {

        return cw[rt];

    }

    int mid = (l + r) >> 1;

    push_down(l, mid, r, rt);

    if(L > mid) return query(L, R, mid+1, r, rson);

    else if(R <= mid) return query(L, R, l, mid, lson);

    else {

        return query(L,mid,l,mid,lson)*query(mid+1,R,mid+1,r,rson);

    }

}

int main() {

    two[0] = 1, mp[1] = 1;

    for(int i = 1; i <= 17; ++i) two[i] = two[i-1] << 1, mp[1<<i] = i + 1;

    scanf("%d%d", &n, &Q);

    for(int i = 1; i < n; ++i) {

        for(int j = 0; j < 3; ++j) for(int k = 0; k < 3; ++k) scanf("%d", &ar[i][j][k]);

    }

    m = 2;

    while(m < n) m <<= 1;

    build(1, m, 1);

    int opt, l, r;

    for(int i = 1; i <= Q; ++i) {

        scanf("%d%d%d", &node[i].opt, &node[i].l, &node[i].r);

        if(node[i].opt == 1) {

            for(int k = 0; k < 3; ++k) for(int j = 0; j < 3; ++j) {

                scanf("%d", &node[i].ar[k][j]);

                tp[i][0].sum[k][j] = node[i].ar[k][j];

            }

            for(int k = 1; k <= 17; ++k) {

                tp[i][k] = tp[i][k-1] * tp[i][k-1];

            }

            update(node[i].l, node[i].r, i, 1, m, 1);

        }else {

            LL ans = 0;

            lp a = query(node[i].l, node[i].r-1, 1, m, 1);

            for(int i = 0; i < 3; ++i) for(int j = 0; j < 3; ++j) ans = (ans + a.sum[i][j]) % mod;

            printf("%lld\n", ans);

        }

    }

    return 0;

}

巴特西

Wannafly Winter Camp Day8(Div1,onsite) E题 Souls-like Game 线段树矩阵乘法

Catalog

Problem：传送门

Solution：

AC_Code：

Problem Description：

最新文章

热门文章

巴特西

Wannafly Winter Camp Day8(Div1,onsite) E题 Souls-like Game 线段树 矩阵乘法

Catalog

Problem：传送门

Solution：

AC_Code：

Problem Description：

最新文章

热门文章

Wannafly Winter Camp Day8(Div1,onsite) E题 Souls-like Game 线段树矩阵乘法