結果

問題 No.879 Range Mod 2 Query
ユーザー startcppstartcpp
提出日時 2019-09-06 23:13:42
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 4,504 bytes
コンパイル時間 1,320 ms
コンパイル使用メモリ 84,668 KB
実行使用メモリ 814,544 KB
最終ジャッジ日時 2023-09-07 03:45:29
合計ジャッジ時間 7,159 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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)];
	queue<P> lazy[1 << (DEPTH + 1)];
	
	SegTree() {
		int i;
		rep(i, 1 << (DEPTH + 1)) {
			node[i] = 0;
			while (!lazy[i].empty()) lazy[i].pop();
		}
	}
	
	//k番目のノードについて遅延評価 : 区間[l, r)
	void eval_add(int k, int l, int r, int x) {
		node[k] += (r - l) * x;
		if (r - l > 1) {
			lazy[2 * k + 1].push(P(0, x));
			lazy[2 * k + 2].push(P(0, x));
		}
	}
	
	void eval_update(int k, int l, int r) {
		node[k] = 0;
		if (r - l > 1) {
			lazy[2 * k + 1].push(P(1, 0));
			lazy[2 * k + 2].push(P(1, 0));
		}
	}
	
	//k番目のノードについて遅延評価 : 区間[l, r)
	void eval(int k, int l, int r) {
		while (!lazy[k].empty()) {
			P now = lazy[k].front();
			int val = now.second;
			lazy[k].pop();
			
			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].push(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].push(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