結果

問題 No.2611 Count 01
ユーザー Carpenters-CatCarpenters-Cat
提出日時 2024-01-20 00:59:11
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,504 bytes
コンパイル時間 4,211 ms
コンパイル使用メモリ 267,260 KB
実行使用メモリ 98,620 KB
最終ジャッジ日時 2024-09-28 05:19:55
合計ジャッジ時間 16,566 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = __int128;
#include <atcoder/all>
using namespace atcoder;
struct S {
	ll sum;
	ll b0;
	ll b1;
	ll a0;
	ll a1;
	ll n0;
	ll n1;
	ll sum_b;
	ll sum_a;
};
S op(S a, S b) {
	S c = S{0, 0, 0, 0, 0, 0, 0, 0, 0};
	ll al = a.n0 + a.n1, bl = b.n0 + b.n1;
	c.sum = a.sum + (a.sum_b * bl) + b.sum + (b.sum_a * al) + a.b0 * b.a1 + a.b1 * b.a0;
	c.b0 = a.b0 + (b.b0 + al * b.n0);
	c.b1 = a.b1 + (b.b1 + al * b.n1);
	c.a0 = b.a0 + (a.a0 + bl * a.n0);
	c.a1 = b.a1 + (a.a1 + bl * a.n1);
	c.n0 = a.n0 + b.n0;
	c.n1 = a.n1 + b.n1;
	c.sum_b = a.sum_b + (b.sum_b + b.n0 * b.n1 * al) + a.b0 * b.n1 + a.b1 * b.n0;
	c.sum_a = b.sum_a + (a.sum_a + a.n0 * a.n1 * bl) + b.a0 * a.n1 + b.a1 * a.n0;
	return c;
}
S e() {
	return S{0, 0, 0, 0, 0, 0, 0, 0, 0};
}
S one0() {
	return S{0, 1, 0, 1, 0, 1, 0, 0, 0};
}
S one1() {
	return S{0, 0, 1, 0, 1, 0, 1, 0, 0};
}
S one(int a) {
	return (a ? one1() : one0());
}
string to_string(ll a) {
	string r;
	while(a) {
		r += '0' + (char)(a % 10);
		a /= 10;
	}
	reverse(r.begin(), r.end());
	return r;
}
int main () {
	int N, Q;
	cin >> N >> Q;
	string s;
	cin >> s;
	std::vector<S> A(N);
	for (int i = 0; i < N; i ++) {
		A[i] = one(s[i] - '0');
	}
	segtree<S, op, e> sg(A);
	while (Q--) {
		int t;
		cin >> t;
		if (t - 1) {
			int l, r;
			cin >> l >> r;
			l --;
			cout << to_string(sg.prod(l, r).sum) << endl;
		} else {
			int i;
			cin >> i;
			i --;
			s[i] = (s[i] == '0' ? '1' : '0');
			sg.set(i, one(s[i] - '0'));
		}
	}
}
0