SPOJ 2211 - Mars Map

問題文 : Mars Map

解法 :
座標において長方形が重なっている領域の面積を求める問題. 平面走査を行った.

具体的には, ある長方形について, (x1, y1, y2)の間その領域を存在することにして, (x2, y1, y2)をその領域を消すタイミングとする.これをO(logN)で実現することが目標である.

・区間[p, q]に値を足す.
・区間[p, q]で, 0でない要素の数を数える.

という処理が行えれば良い. これは, 和を持つセグメント木を工夫することで実現できる.

0でない要素の個数は, 0である要素の個数さえ求まればわかるので, セグメント木の節点が0である要素を数える関数を実装し, 答えを求める.

これで, O(N log N)時間でこの問題を解くことが出来る. もっと効率良い方法あるよねこれ.

コード :

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long lint;

struct Event {
	int x, y1, y2;
	int pm;
	
	Event(int x, int y1, int y2, int pm) : x(x), y1(y1), y2(y2), pm(pm){}
	Event(){}
};

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

typedef struct {
	int val;
	int plus;
} Node;

Node seg[1 << 20];

inline void evaluate(int k, int a, int b)
{
	seg[k].val += (b - a) * seg[k].plus;
	
	if (k < (1 << 19) - 1){
		seg[k * 2 + 1].plus += seg[k].plus;
		seg[k * 2 + 2].plus += seg[k].plus;
	}
	seg[k].plus = 0;
}

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

void add(int a, int b, int x, int k = 0, int l = 0, int r = 1 << 19)
{
	evaluate(k, l, r);
	
	if (b <= l || r <= a) return;
	
	if (a <= l && r <= b){
		seg[k].plus += x;
		evaluate(k, l, r);
		return;
	}
	
	add(a, b, x, k * 2 + 1, l, (l + r) / 2);
	add(a, b, x, k * 2 + 2, (l + r) / 2, r);
	_update(k);
}

int countZero(int k = 0, int l = 0, int r = 1 << 19)
{
	evaluate(k, l, r);
	
	if (k >= (1 << 19) - 1){
		return (!seg[k].val);
	}
	
	if (seg[k].val == 0) return (r - l);
	
	return (countZero(k * 2 + 1, l, (l + r) / 2) + countZero(k * 2 + 2, (l + r) / 2, r));
}

int main()
{
	int n;
	Event e[20000];
	
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++){
		int x1, y1, x2, y2;
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		e[i * 2] = Event(x1, y1, y2, 1);
		e[i * 2 + 1] = Event(x2, y1, y2, -1);
	}
	
	sort(e, e + 2 * n);
	
	int res = 0;
	
	add(e[0].y1, e[0].y2, e[0].pm);
	
	for (int i = 1; i < 2 * n; i++){
		int all = (1 << 19) - countZero();
		res += (e[i].x - e[i - 1].x) * all;
		add(e[i].y1, e[i].y2, e[i].pm);
	}
	printf("%d\n", res);
	
	return (0);
}

(追記)

↑のcountZero, 最悪ケースが普通にO(N)でTLEしていたので, logNになるように遅延評価をいじりました.

コード:

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long lint;

struct Event {
	int x, y1, y2;
	int pm;
	
	Event(int x, int y1, int y2, int pm) : x(x), y1(y1), y2(y2), pm(pm){}
	Event(){}
};

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

typedef struct _node {
	int val, plus, zero;
} Node;

Node seg[1 << 20];

inline void evaluate(int k, int a, int b)
{
	seg[k].val += seg[k].plus;
	
	if (k < (1 << 19) - 1){
		seg[k * 2 + 1].plus += seg[k].plus;
		seg[k * 2 + 2].plus += seg[k].plus;
	}
	seg[k].plus = 0;
}

void _update(int k)
{
	seg[k].val = min(seg[k * 2 + 1].val, seg[k * 2 + 2].val);
	seg[k].zero = 0;
	if (seg[k * 2 + 1].val == seg[k].val) seg[k].zero += seg[k * 2 + 1].zero;
	if (seg[k * 2 + 2].val == seg[k].val) seg[k].zero += seg[k * 2 + 2].zero;
}

void add(int a, int b, int x, int k = 0, int l = 0, int r = 1 << 19)
{
	evaluate(k, l, r);
	
	if (b <= l || r <= a) return;
	
	if (a <= l && r <= b){
		seg[k].plus += x;
		evaluate(k, l, r);
		return;
	}
	
	add(a, b, x, k * 2 + 1, l, (l + r) / 2);
	add(a, b, x, k * 2 + 2, (l + r) / 2, r);
	_update(k);
}

int main()
{
	int n;
	Event e[20000];
	
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++){
		int x1, y1, x2, y2;
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		e[i * 2] = Event(x1, y1, y2, 1);
		e[i * 2 + 1] = Event(x2, y1, y2, -1);
	}
	
	sort(e, e + 2 * n);
	
	for (int i = 0; i < 1 << 19; i++) seg[i + (1 << 19) - 1].zero = 1;
	for (int i = (1 << 19) - 2; i >= 0; i--) seg[i].zero = seg[i * 2 + 1].zero + seg[i * 2 + 2].zero;
	
	int res = 0;
	
	add(e[0].y1, e[0].y2, e[0].pm);
	
	for (int i = 1; i < 2 * n; i++){
		int all = (1 << 19) - seg[0].zero;
		res += (e[i].x - e[i - 1].x) * all;
		add(e[i].y1, e[i].y2, e[i].pm);
	}
	printf("%d\n", res);
	
	return (0);
}