結果

問題 No.879 Range Mod 2 Query
ユーザー startcppstartcpp
提出日時 2019-09-06 23:37:45
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 4,541 bytes
コンパイル時間 807 ms
コンパイル使用メモリ 73,512 KB
実行使用メモリ 12,860 KB
最終ジャッジ日時 2023-09-07 03:56:04
合計ジャッジ時間 4,530 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

//まあ冷静になれば、そうですねぇ。Σa[i] % 2 (l≦i≦r)を求めるなら簡単なので、
//b[i] + Σa[i] % 2 (l≦i≦r)を求める問題だと思ってやると、b[i]に対して「区間を全て0にする」「区間にxを足す」
//ができればよく、これはRange Update Queryなので、はい。
//えー。Range Update Query、解いた記憶ないが。
//というわけで一から考えると、これは遅延セグ木で解けそうな形をしてそう。
//時刻が小さい順にクエリを実行していけば無難っぽさがある。
//これは遅延させているクエリをqueueで管理することで簡単に実現できる。
//遅延セグ木は…[http://tsutaj.hatenablog.com/entry/2017/03/30/224339] ありがてぇ。
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#define int long long
#define rep(i, n) for(i = 0; i < (n); i++)
using namespace std;

const int DEPTH = 17;

struct SegMod2 {
	int oddNum[1 << (DEPTH + 1)];
	bool lazy[1 << (DEPTH + 1)];
	
	SegMod2() {
		int i;
		rep(i, 1 << (DEPTH + 1)) {
			oddNum[i] = 0;
			lazy[i] = 0;
		}
	}
	
	//k番目のノードについて遅延評価 : 区間[l, r)
	void eval(int k, int l, int r) {
		if (lazy[k]) {
			oddNum[k] = r - l - oddNum[k];
			if (r - l > 1) {
				lazy[2 * k + 1] = !lazy[2 * k + 1];
				lazy[2 * k + 2] = !lazy[2 * k + 2];
			}
			lazy[k] = false;
		}
	}
	
	void flip(int l, int r, int a = 0, int b = (1 << DEPTH), int id = 0) {
		eval(id, a, b);
		
		if (a >= r || b <= l) return;
		
		if (a <= l && r <= b) {
			lazy[id] = !lazy[id];
			eval(id, a, b);
		}
		else {
			flip(l, r, a, (a + b) / 2, id * 2 + 1);
			flip(l, r, (a + b) / 2, b, id * 2 + 2);
		}
	}
	
	int sum(int l, int r, int a = 0, int b = (1 << DEPTH), int id = 0) {
		if (a >= r || b <= l) return 0;
		
		eval(id, a, b);
		if (l <= a && b <= r) return oddNum[id];
		int vl = sum(l, r, a, (a + b) / 2, id * 2 + 1);
		int vr = sum(l, r, (a + b) / 2, b, id * 2 + 2);
		return vl + vr;
	}
};

typedef pair<int, int> P;	//(query_type, value), type = 0:可算, type = 1:更新
struct SegTree {
	int node[1 << (DEPTH + 1)];
	P lazy[1 << (DEPTH + 1)];
	
	SegTree() {
		int i;
		rep(i, 1 << (DEPTH + 1)) {
			node[i] = 0;
			lazy[i] = P(0, 0);
		}
	}
	
	//k番目のノードについて遅延評価 : 区間[l, r)
	void eval_add(int k, int l, int r, int x) {
		node[k] += (r - l) * x;
		if (r - l > 1) {
			if (lazy[2 * k + 1].second == 1) { eval_update(2 * k + 1, l, (l + r) / 2); }
			lazy[2 * k + 1] = P(0, x);
			if (lazy[2 * k + 2].second == 1) { eval_update(2 * k + 2, (l + r) / 2, r); }
			lazy[2 * k + 2] = P(0, x);
		}
	}
	
	void eval_update(int k, int l, int r) {
		node[k] = 0;
		if (r - l > 1) {
			lazy[2 * k + 1] = P(1, 0);
			lazy[2 * k + 2] = P(1, 0);
		}
	}
	
	//k番目のノードについて遅延評価 : 区間[l, r)
	void eval(int k, int l, int r) {
		if (lazy[k].first == 0 && lazy[k].second == 0) return;
		P now = lazy[k];
		int val = now.second;
		lazy[k] = P(0, 0);
		
		if (now.first == 0) {
			eval_add(k, l, r, val);
		}
		else {
			eval_update(k, l, r);
		}
	}
	
	//加算
	void add(int l, int r, int x, int a = 0, int b = (1 << DEPTH), int id = 0) {
		eval(id, a, b);
		
		if (a >= r || b <= l) return;
		
		if (a <= l && r <= b) {
			lazy[id] = P(0, x);
			eval(id, a, b);
		}
		else {
			add(l, r, x, a, (a + b) / 2, id * 2 + 1);
			add(l, r, x, (a + b) / 2, b, id * 2 + 2);
		}
	}
	
	//リゼロ
	void update(int l, int r, int a = 0, int b = (1 << DEPTH), int id = 0) {
		eval(id, a, b);
		
		if (a >= r || b <= l) return;
		
		if (a <= l && r <= b) {
			lazy[id] = P(1, 0);
			eval(id, a, b);
		}
		else {
			update(l, r, a, (a + b) / 2, id * 2 + 1);
			update(l, r, (a + b) / 2, b, id * 2 + 2);
		}
	}
	
	//わーーっ
	int sum(int l, int r, int a = 0, int b = (1 << DEPTH), int id = 0) {
		if (a >= r || b <= l) return 0;
		
		eval(id, a, b);
		if (l <= a && b <= r) return node[id];
		int vl = sum(l, r, a, (a + b) / 2, id * 2 + 1);
		int vr = sum(l, r, (a + b) / 2, b, id * 2 + 2);
		return vl + vr;
	}
};

int n, q;
int a[100000];
SegMod2 segMod2;
SegTree seg;

signed main() {
	int i;
	
	cin >> n >> q;
	rep(i, n) cin >> a[i];
	rep(i, q) {
		int t, l, r, x;
		cin >> t >> l >> r;
		l--; r--;
		if (t == 1) {
			seg.update(l, r + 1);
		}
		if (t == 2) {
			cin >> x;
			seg.add(l, r + 1, x);
			if (x % 2 == 1) {
				segMod2.flip(l, r + 1);
			}
		}
		if (t == 3) {
			cout << segMod2.sum(l, r + 1) + seg.sum(l, r + 1) << endl;
		}
	}
	return 0;
}
0