結果

問題 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';
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0