結果

問題 No.2611 Count 01
ユーザー hitonanodehitonanode
提出日時 2024-01-19 22:56:14
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 226 ms / 6,000 ms
コード長 1,787 bytes
コンパイル時間 1,051 ms
コンパイル使用メモリ 123,112 KB
実行使用メモリ 29,820 KB
最終ジャッジ日時 2024-09-28 04:56:50
合計ジャッジ時間 7,334 ms
ジャッジサーバーID
（参考情報） 		judge3 / 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 222 ms
29,692 KB
testcase_04 AC 222 ms
29,692 KB
testcase_05 AC 226 ms
29,796 KB
testcase_06 AC 220 ms
29,692 KB
testcase_07 AC 218 ms
29,692 KB
testcase_08 AC 216 ms
29,692 KB
testcase_09 AC 224 ms
29,692 KB
testcase_10 AC 216 ms
29,692 KB
testcase_11 AC 217 ms
29,692 KB
testcase_12 AC 226 ms
29,696 KB
testcase_13 AC 213 ms
29,728 KB
testcase_14 AC 212 ms
29,772 KB
testcase_15 AC 220 ms
29,560 KB
testcase_16 AC 215 ms
29,820 KB
testcase_17 AC 214 ms
29,820 KB
testcase_18 AC 210 ms
29,692 KB
testcase_19 AC 215 ms
29,696 KB
testcase_20 AC 210 ms
29,692 KB
testcase_21 AC 209 ms
29,692 KB
testcase_22 AC 223 ms
29,692 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)

#include <atcoder/modint>
#include <atcoder/segtree>
using mint = atcoder::modint998244353;

struct S {
    mint n0;
    mint l0;
    mint r0;

    mint n1;
    mint l1;
    mint r1;

    mint in01s;

    mint l01;
    mint r01;

    mint ret;

    mint n() const { return n0 + n1; }

    static S gen(char x) {
        if (x == '0') return S{1, 1, 1, 0, 0, 0, 0, 0, 0, 0};
        if (x == '1') return S{0, 0, 0, 1, 1, 1, 0, 0, 0, 0};
        assert(false);
    }
};

S op(S l, S r) {
    return S{
        l.n0 + r.n0,
        l.l0 + r.l0 + l.n() * r.n0,
        l.r0 + r.r0 + l.n0 * r.n(),
        l.n1 + r.n1,
        l.l1 + r.l1 + l.n() * r.n1,
        l.r1 + r.r1 + l.n1 * r.n(),
        l.in01s + r.in01s + l.n0 * r.n1 + l.n1 * r.n0,
        l.l01 + r.l01 + l.l1 * r.n0 + l.l0 * r.n1 + l.n() * r.in01s,
        l.r01 + r.r01 + r.r0 * l.n1 + r.r1 * l.n0 + r.n() * l.in01s,
        l.ret + r.ret + l.l01 * r.n() + l.n() * r.r01 + l.l0 * r.r1 + l.l1 * r.r0,
    };
}
S e() { return S{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; }

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int N, Q;
    string str;
    cin >> N >> Q >> str;
    vector<S> init;
    for (auto c : str) init.emplace_back(S::gen(c));
    atcoder::segtree<S, op, e> tree(init);

    while (Q--) {
        int tp;
        cin >> tp;
        if (tp == 1) {
            int i;
            cin >> i;
            --i;
            str.at(i) ^= 1;
            tree.set(i, S::gen(str.at(i)));
        } else {
            int l, r;
            cin >> l >> r;
            --l;
            cout << tree.prod(l, r).ret.val() << '\n';
        }
    }
}
0