結果

問題 No.2611 Count 01
コンテスト
ユーザー kwm_t
提出日時 2024-01-19 23:42:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 515 ms / 6,000 ms
コード長 2,639 bytes
コンパイル時間 4,506 ms
コンパイル使用メモリ 257,580 KB
最終ジャッジ日時 2025-02-18 21:36:29
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
const int mod = 998244353;
//using mint = modint1000000007;
//const int mod = 1000000007;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n-1); i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
struct S {
	mint l0, l1, ls;
	mint r0, r1, rs;
	mint c0, c1;
	mint val, size;
	S() {}
	S op(const S &other) {
		S s;
		s.l0 = l0 + other.l0 + c0 * other.size;
		s.l1 = l1 + other.l1 + c1 * other.size;
		s.ls = ls + other.ls + c1 * other.l0 + c0 * other.l1 + c0 * c1 * other.size;

		s.r0 = r0 + other.r0 + other.c0 *size;
		s.r1 = r1 + other.r1 + other.c1 * size;
		s.rs = rs + other.rs + other.c1 * r0 + other.c0 * r1 + other.c0 * other.c1 * size;

		s.c0 = c0 + other.c0;
		s.c1 = c1 + other.c1;

		s.size = size + other.size;
		s.val = val + other.val + size * other.ls + other.size * rs + r0 * other.l1 + r1 * other.l0;
		return s;
	}
	static S e0() {
		S s = e();
		s.r0 = 1;
		s.l0 = 1;
		s.c0 = 1;
		s.size = 1;
		return s;
	}
	static S e1() {
		S s = e();
		s.r1 = 1;
		s.l1 = 1;
		s.c1 = 1;
		s.size = 1;
		return s;
	}
	static S e() {
		S s;
		s.l0 = 0, s.l1 = 0, s.ls = 0;
		s.r0 = 0, s.r1 = 0, s.rs = 0;
		s.c0 = 0, s.c1 = 0;
		s.val = 0, s.size = 0;
		return s;
	}
	void debug() {
		cout << l0.val() << " " << l1.val() << endl;
		cout << r0.val() << " " << r1.val() << endl;
		cout << c0.val() << " " << c1.val() << endl;
		cout << size.val() << " " << val.val() << endl;
		cout << endl;
	}
};
S op(S a, S b) { return a.op(b); }
S e() { return S::e(); }
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q; cin >> n >> q;
	string s; cin >> s;
	segtree<S, op, e>seg(n);
	rep(i, n) {
		if ('0' == s[i]) seg.set(i, S::e0());
		else  seg.set(i, S::e1());
	}
	while (q--) {
		int t; cin >> t;
		if (1 == t) {
			int i; cin >> i;
			i--;
			if ('0' == s[i]) {
				seg.set(i, S::e1());
				s[i] = '1';
			}
			else {
				seg.set(i, S::e0());
				s[i] = '0';
			}
		}
		else {
			int l, r; cin >> l >> r;
			l--, r--;
			auto get = seg.prod(l, r + 1);
			cout << get.val.val() << endl;
		}
	}
	return 0;
}
0