#942120 (C++23) No.2611 Count 01

• 問題: No.2611 Count 01
• ユーザー: Mitarushi
• 提出日時: 2024-01-07 15:56:59
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 592 ms / 6,000 ms
• コード長: 4,441 bytes
• コンパイル時間: 1,309 ms
• コンパイル使用メモリ: 84,392 KB
• 実行使用メモリ: 151,040 KB
• 最終ジャッジ日時: 2024-09-28 03:35:01
• 合計ジャッジ時間: 15,203 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 20

ソースコード

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <array>

template <typename T, typename U>
struct SegmentTree {
    int n;
    std::vector<T> data;
    T e;

    SegmentTree(int n, T e) : e(e) {
        int n2 = 1;
        while (n2 < n) {
            n2 *= 2;
        }
        this->n = n2;
        this->data = std::vector<T>(n2 * 2, e);
    }

    void build() {
        for (int i = this->n - 1; i >= 1; i--) {
            this->data[i] = this->data[i * 2] + this->data[i * 2 + 1];
        }
    }

    void update(int i, T x) {
        int k = i + this->n;
        this->data[k] = x;
        while (k > 1) {
            k /= 2;
            this->data[k] = this->data[k * 2] + this->data[k * 2 + 1];
        }
    }

    auto query(int l, int r, U ls, U rs) {
        l += this->n;
        r += this->n;
        while (l < r) {
            if (l & 1) {
                ls = ls + this->data[l];
                l++;
            }
            if (r & 1) {
                r--;
                rs = this->data[r] + rs;
            }
            l /= 2;
            r /= 2;
        }
        return ls + rs;
    }
};

using int64 = std::int64_t;
constexpr int64 MOD = 998244353;

struct Vec {
    std::array<int64, 6> data;

    Vec() {
        std::fill_n(this->data.begin(), 6, 0);
    }

    Vec(const int (&a)[6]) {
        std::copy_n(a, 6, this->data.begin());
    }
};

struct Matrix {
    std::array<std::array<int64, 6>, 6> data;

    Matrix() {
        std::fill_n(this->data.begin(), 6, std::array<int64, 6>());
        for (int i = 0; i < 6; i++) {
            std::fill_n(this->data[i].begin(), i + 1, 0);
        }
    }

    Matrix(const int (&a)[6][6]) {
        for (int i = 0; i < 6; i++) {
            std::copy_n(a[i], i + 1, this->data[i].begin());
        }
    }
};

Matrix operator+(const Matrix &a, const Matrix &b) {
    Matrix result;
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j <= i; j++) {
            for (int k = j; k <= i; k++) {
                result.data[i][j] += a.data[i][k] * b.data[k][j];
            }
            result.data[i][j] %= MOD;
        }
    }
    return result;
}

Vec operator+(const Vec &a, const Matrix &b) {
    Vec result;
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j <= i; j++) {
            result.data[j] += a.data[i] * b.data[i][j];
        }
    }
    for (int i = 0; i < 6; i++) {
        result.data[i] %= MOD;
    }
    return result;
}

Vec operator+(const Matrix &a, const Vec &b) {
    Vec result;
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j <= i; j++) {
            result.data[i] += a.data[i][j] * b.data[j];
        }
    }
    for (int i = 0; i < 6; i++) {
        result.data[i] %= MOD;
    }
    return result;
}

int64 operator+(const Vec &a, const Vec &b) {
    int64 result = 0;
    for (int i = 0; i < 6; i++) {
        result += a.data[i] * b.data[i];
    }
    return result % MOD;
}

const std::array<Matrix, 2> node = {{
    Matrix({
        {1, 0, 0, 0, 0, 0},
        {1, 1, 0, 0, 0, 0},
        {1, 1, 1, 0, 0, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 1, 1, 0},
        {0, 0, 0, 1, 1, 1},
    }),
    Matrix({
        {1, 0, 0, 0, 0, 0},
        {1, 1, 0, 0, 0, 0},
        {0, 0, 1, 0, 0, 0},
        {1, 1, 0, 1, 0, 0},
        {0, 0, 1, 0, 1, 0},
        {0, 0, 1, 0, 1, 1},
    })
}};

const Matrix identity = Matrix({
    {1, 0, 0, 0, 0, 0},
    {0, 1, 0, 0, 0, 0},
    {0, 0, 1, 0, 0, 0},
    {0, 0, 0, 1, 0, 0},
    {0, 0, 0, 0, 1, 0},
    {0, 0, 0, 0, 0, 1},
});

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    std::vector<int> s(n);
    for (int i = 0; i < n; i++) {
        char c;
        scanf(" %c", &c);
        s[i] = c - '0';
    }
    SegmentTree<Matrix, Vec> st(n, identity);

    for (int i = 0; i < n; i++) {
        st.data[i + st.n] = node[s[i]];
    }
    st.build();
    
    for (int i = 0; i < q; i++) {
        int t;
        scanf("%d", &t);
        if (t == 1) {
            int j;
            scanf("%d", &j);
            j--;
            s[j] = 1 - s[j];
            st.update(j, node[s[j]]);
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            l--;
            int64 ans = st.query(l, r, Vec({0, 0, 0, 0, 0, 1}), Vec({1, 0, 0, 0, 0, 0}));
            printf("%lld\n", ans);
        }
    }
}