JOI春合宿 2012-day3 fortune telling

問題文 : 占い

解法 :
あるカードを奇数回ひっくり返せばそのカードは裏で, 偶数回ひっくり返せばそのカードは表である.

これは, カードをひっくり返す順序によらないので, y1 ≦ y ≦ y2 行 x1 ≦ x ≦ x2列のカード
をひっくり返す, という命令を
x1 ≦ x ≦ x2という区間を, y1でひっくり返し, y2 + 1でもとに戻す, というイベントとして扱う.

イベント化した後はyの順序でソートする. こうすることで, O(M)個のセグメント木を持たずに1個のセグメント木だけでひっくり返す操作を行うことが出来る.
O(M)回のひっくり返す操作は, セグメント木と用いて一回の操作をO(logM)時間で行うことが出来る.

ゆえに, このプログラムは, O(MlogM)時間で動作する.

コード :

#include <cstdio>
#include <map>
#include <algorithm>

typedef long long lint;

using namespace std;

struct Node {
	bool flip;
	lint val;
	Node(){
		flip = false;
		val = 0;
	}
};

struct Event {
	int l, r, y;
	Event(){
		l = r = y = 0;
	}
	Event(int l, int r, int y) : l(l), r(r), y(y) {}
};

Node seg[1 << 19];
lint cmp[200000];
int sz;

void init(int n)
{
	sz = 1;
	while (sz < n){
		sz *= 2;
	}
}

inline void evaluate(int k, int a, int b)
{
	if (seg[k].flip) seg[k].val = (cmp[b] - cmp[a]) - seg[k].val;
	
	if (k < sz - 1){
		seg[k * 2 + 1].flip ^= seg[k].flip;
		seg[k * 2 + 2].flip ^= seg[k].flip;
	}
	seg[k].flip = false;
}

void _update(int k)
{
	seg[k].val = seg[k * 2 + 1].val + seg[k * 2 + 2].val;
}

void update(int a, int b, int k = 0, int l = 0, int r = sz)
{
	evaluate(k, l, r);
	
	if (b <= l || r <= a) return;
	
	if (a <= l && r <= b){
		seg[k].flip ^= 1;
		evaluate(k, l, r);
		return;
	}
	update(a, b, k * 2 + 1, l, (l + r) / 2);
	update(a, b, k * 2 + 2, (l + r) / 2, r);
	_update(k);
	
	return;
}

lint getSum(int a, int b, int k = 0, int l = 0, int r = sz)
{
	evaluate(k, l, r);
	
	if (b <= l || r <= a) return (0);
	
	if (a <= l && r <= b){
		evaluate(k, l, r);
		return (seg[k].val);
	}
	
	lint lch = getSum(a, b, k * 2 + 1, l, (l + r) / 2);
	lint rch = getSum(a, b, k * 2 + 2, (l + r) / 2, r);
	_update(k);
	
	return (lch + rch);
}

bool operator < (const Event &a, const Event &b)
{
	return (a.y < b.y);
}


int x1[100000], x2[100000], y1[100000], y2[100000];
int xs[200000];
Event ev[200000];

int main()
{
	int m, n, k;
	int idx;
	map<int, int> mp;
	
	scanf("%d %d %d", &m, &n, &k);
	
	for (int i = 0; i < k; i++){
		scanf("%d %d %d %d", y1 + i, y2 + i, x1 + i, x2 + i);
		x1[i]--; y1[i]--;
		xs[i * 2] = x1[i];
		xs[i * 2 + 1] = x2[i];
	}
	
	sort(xs, xs + 2 * k);
	mp[xs[0]] = idx = 0;
	cmp[0] = xs[0];
	for (int i = 1; i < k * 2; i++){
		if (xs[i] != xs[i - 1]){
			mp[xs[i]] = ++idx;
			cmp[idx] = xs[i];
		}
	}
	
	for (int i = 0; i < k; i++){
		ev[i * 2] = Event(mp[x1[i]], mp[x2[i]], y1[i]);
		ev[i * 2 + 1] = Event(mp[x1[i]], mp[x2[i]], y2[i]);
	}
	
	sort(ev, ev + k * 2);
	
	init(++idx);
	
	lint ret = 0;
	update(ev[0].l, ev[0].r);
	for (int i = 1; i < k * 2; i++){
		ret += (ev[i].y - ev[i - 1].y) * getSum(0, idx);
		update(ev[i].l, ev[i].r);
	}
	
	printf("%lld\n", (lint)m * n - ret);
	
	return (0);
}