結果

問題 No.879 Range Mod 2 Query
ユーザー QCFiumQCFium
提出日時 2019-09-06 23:07:35
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,047 bytes
コンパイル時間 2,078 ms
コンパイル使用メモリ 178,528 KB
実行使用メモリ 9,984 KB
最終ジャッジ日時 2024-06-24 22:21:09
合計ジャッジ時間 5,066 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
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 -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

struct SegTree {
	std::vector<int64_t> data; // sum
	std::vector<int> odds; // num of odds
	std::vector<int64_t> lazy; // lazy
	std::vector<bool> lazyf;// lazy of flush
	std::vector<int> num;
	int n;
	SegTree (const std::vector<int> &a) {
		for (n = 1; n < (int) a.size(); n *= 2);
		data.resize(2 * n);
		odds.resize(2 * n);
		lazy.resize(2 * n);
		lazyf.resize(2 * n);
		num.resize(2 * n);
		for (int i = 0; i < (int) a.size(); i++) data[i + n] = a[i], odds[i + n] = a[i] & 1;
		for (int i = n; i < 2 * n; i++) num[i] = 1;
		for (int i = n - 1; i; i--) update(i), num[i] = num[i << 1] * 2;
	}
	void flush_(int i) {
		if (lazy[i]) {
			data[i] += (int64_t) num[i] * lazy[i];
			if (lazy[i] & 1) odds[i] = num[i] - odds[i];
			if (i < n) {
				flushf(i << 1);
				flushf(i << 1 | 1);
				lazy[i << 1] += lazy[i];
				lazy[i << 1 | 1] += lazy[i];
			}
			lazy[i] = 0;
		}
	}
	void flushf(int i) {
		if (lazyf[i]) {
			lazy[i] = 0;
			data[i] = odds[i];
			if (i < n) {
				lazyf[i << 1] = true;
				lazyf[i << 1 | 1] = true;
			}
			lazyf[i] = false;
		}
	}
	void flush(int i) {
		flushf(i);
		flush_(i);
	}
	void update(int i) {
		if (i < n) {
			data[i] = data[i << 1] + data[i << 1 | 1];
			odds[i] = odds[i << 1] + odds[i << 1 | 1];
		}
	}
	void add(int l, int r, int x, int i = 1, int node_l = 0, int node_r = 0) {
		if (l == r) return;
		if (!node_r) node_r = n;
		flush(i);
		if (l == node_l && r == node_r) {
			lazy[i] += x;
			flush(i);
			return;
		}
		if (r <= node_l || l >= node_r) return;
		int mid = node_l + (node_r - node_l) / 2;
		add(std::max(node_l, l), std::min(mid, r), x, i << 1, node_l, mid);
		add(std::max(mid, l), std::min(node_r, r), x, i << 1 | 1, mid, node_r);
		update(i);
	}
	void mod2(int l, int r, int i = 1, int node_l = 0, int node_r = 0) {
		if (l == r) return;
		if (!node_r) node_r = n;
		flush(i);
		if (l == node_l && r == node_r) {
			lazyf[i] = true;
			flush(i);
			return;
		}
		if (r <= node_l || l >= node_r) return;
		int mid = node_l + (node_r - node_l) / 2;
		mod2(std::max(node_l, l), std::min(mid, r), i << 1, node_l, mid);
		mod2(std::max(mid, l), std::min(node_r, r), i << 1 | 1, mid, node_r);
		update(i);
	}
	int64_t sum(int l, int r, int i = 1, int node_l = 0, int node_r = 0) {
		if (l == r) return 0;
		if (!node_r) node_r = n;
		flush(i);
		if (l == node_l && r == node_r) return data[i];
		if (r <= node_l || l >= node_r) return 0;
		int mid = node_l + (node_r - node_l) / 2;
		return 
		sum(std::max(node_l, l), std::min(mid, r), i << 1, node_l, mid) + 
		sum(std::max(mid, l), std::min(node_r, r), i << 1 | 1, mid, node_r);
	}
};

int main() {
	int n = ri();
	int q = ri();
	std::vector<int> a(n);
	for (int i = 0; i < n; i++) a[i] = ri();
	SegTree tree(a);
	for (int i = 0; i < q; i++) {
		int t = ri();
		int l = ri() - 1, r = ri() - 1;
		if (t == 1) {
			tree.mod2(l, r + 1);
		} else if (t == 2) {
			tree.add(l, r + 1, ri());
		} else printf("%lld\n", (long long) tree.sum(l, r + 1));
	}
	return 0;
}
0