結果

問題 No.2611 Count 01
ユーザー hitonanode
提出日時 2024-01-19 22:56:14
言語 C++23
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

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