2024牛客寒假算法基础集训营4 K.方块掉落

线段树维护的信息有当前行有多少方块， 一共有多少方块

拿线段树维护一个矩阵就行，转移更新就是矩阵乘

类似题有这个 牛客多校第二场-H - zhujio

两题都基本上就是转移矩阵求出来正常建线段树， pushup就是直接矩阵乘

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
typedef long long ll;

const int sz = 3;
const int mod = 1e9 + 7;
const int N = 2e5 + 100;

struct mat {
    ll m[sz][sz];

//可能还要有mod

    mat() { memset(m, 0, sizeof m); }

    mat operator-(const mat& T) const {
        mat res;
        for (int i = 0; i < sz; ++i)
            for (int j = 0; j < sz; ++j) {
                res.m[i][j] = (m[i][j] - T.m[i][j]);
            }
        return res;
    }

    mat operator+(const mat& T) const {
        mat res;
        for (int i = 0; i < sz; ++i)
            for (int j = 0; j < sz; ++j) {
                res.m[i][j] = (m[i][j] + T.m[i][j]);
            }
        return res;
    }

    mat operator*(const mat& T) const {
        mat res;
        int r;
        for (int i = 0; i < sz; ++i)
            for (int k = 0; k < sz; ++k) {
                r = m[i][k];
                for (int j = 0; j < sz; ++j)
                    res.m[i][j] = (res.m[i][j] + T.m[k][j] * r % mod) % mod;
            }
        return res;
    }

    mat operator^(ll x) const {
        mat res, bas;
        for (int i = 0; i < sz; ++i) res.m[i][i] = 1;
        for (int i = 0; i < sz; ++i)
            for (int j = 0; j < sz; ++j) bas.m[i][j] = m[i][j];
        while (x) {
            if (x & 1) res = res * bas;
            bas = bas * bas;
            x >>= 1;
        }
        return res;
    }
} Seg[N * 5], A, B, C, f;

char op[N];

void build(int now, int l, int r) {
    if (l == r) {
        if (op[l] == 'Y') Seg[now] = A;
        else if (op[l] == 'B') Seg[now] = B;
        else Seg[now] = C;
        return;
    }
    int mid = (l + r) >> 1;
    build(now * 2, l, mid);
    build(now * 2 + 1, mid + 1, r);
    Seg[now] = Seg[now * 2] * Seg[now * 2 + 1];
}

void modify(int now, int l, int r, int pos, char v) {
    if (l == r) {
        if (v == 'Y') Seg[now] = A;
        else if (v == 'B') Seg[now] = B;
        else Seg[now] = C;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) modify(now * 2, l, mid, pos, v);
    else modify(now * 2 + 1, mid + 1, r, pos, v);
    Seg[now] = Seg[now * 2] * Seg[now * 2 + 1];
}

mat qurey(int now, int l, int r, int x, int y) {
    if (x <= l && y >= r)return Seg[now];
    int mid = (l + r) >> 1;
    if (y <= mid) return qurey(now * 2, l, mid, x, y);
    if (x > mid) return qurey(now * 2 + 1, mid + 1, r, x, y);
    return qurey(now * 2, l, mid, x, y) * qurey(now * 2 + 1, mid + 1, r, x, y);
}

void solve() {
    int n, q; cin >> n >> q;
    A.m[0][0] = A.m[1][1] = A.m[2][0] = A.m[2][1] = A.m[2][2] = 1;
    B.m[1][1] = B.m[2][0] = B.m[2][1] = B.m[2][2] = 1;
    C.m[1][1] = C.m[2][0] = C.m[2][1] = C.m[2][2] = C.m[0][1] = 1;
    C.m[0][0] = 2;
    f.m[0][2] = 1;
    for (int i = 1; i <= n; i++) cin >> op[i];
    build(1, 1, n);
    while (q--) {
        int op; cin >> op;
        if (op == 1) {
            int p; cin >> p;
            char c; cin >> c;
            modify(1, 1, n, p, c);
        } else {
            int x, y; cin >> x >> y;
            auto ans = f * qurey(1, 1, n, x, y);
            cout << ans.m[0][1] % mod << endl;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    // int T = 1; cin >> T;
    // while (T--) solve();
    solve();

    return 0;
}