結果

問題 No.2611 Count 01
ユーザー MitarushiMitarushi
提出日時 2024-01-07 15:56:59
言語 C++23
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 555 ms
150,892 KB
testcase_04 AC 562 ms
150,824 KB
testcase_05 AC 560 ms
151,040 KB
testcase_06 AC 584 ms
150,912 KB
testcase_07 AC 587 ms
151,040 KB
testcase_08 AC 590 ms
151,040 KB
testcase_09 AC 586 ms
150,912 KB
testcase_10 AC 579 ms
150,912 KB
testcase_11 AC 561 ms
150,960 KB
testcase_12 AC 558 ms
150,816 KB
testcase_13 AC 590 ms
150,912 KB
testcase_14 AC 546 ms
150,912 KB
testcase_15 AC 550 ms
151,040 KB
testcase_16 AC 540 ms
150,992 KB
testcase_17 AC 583 ms
151,040 KB
testcase_18 AC 591 ms
150,912 KB
testcase_19 AC 587 ms
150,912 KB
testcase_20 AC 556 ms
150,812 KB
testcase_21 AC 552 ms
150,912 KB
testcase_22 AC 592 ms
150,912 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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);
        }
    }
}
0