結果
問題 | No.2611 Count 01 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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';}}}