POJ-2482 : Stars in Your Window

問題概要

2次元ボード[0,2^31)*[0,2^31)がある。その内N(<10^4)個のマスには数字が書かれている。H*Wの窓で切り取って数字の和を最大化する問題。

解法

平面走査する。イベントラインは区間への加算をサポートするRMQで持っておけばよい。つまり、点(x,y)を追加するとき[y,y+H)に書かれている数値を足し込む。削除する時は負の値を足し込めばよい。区間加算をサポートするRMQは、区間内に一様に足された数とそれを除いた最大値を各節点で持つようにすればよい。

acceptされたコード

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

template<typename numType>
inline bool updateMax(numType& old, const numType& test) {
	if (old < test) {
		old = test;
		return true;
	}
	return false;
}

inline unsigned int getNextLargestPowerOf2(unsigned int x) {
	x |= (x >> 1);
	x |= (x >> 2);
	x |= (x >> 4);
	x |= (x >> 8);
	x |= (x >> 16);
	return x + 1;
}

const int INF = int(1.05e9); 

struct Data {
	int maxi, add;
	Data(int maxi = 0, int add = 0):
		maxi(maxi), add(add)
	{}
};

struct SegmentTree {
	int size;
	vector<Data> datas;

	void init(int size_){
		size = getNextLargestPowerOf2(size_ - 1);
		datas.assign(2*size - 1, Data());
	}

	int getValue(int from, int to, int k, int l, int r){
		
		if (r <= from || to <= l) {
			return 0;
		}
		
		if (from <= l && r <= to) {
			return datas[k].maxi + datas[k].add;
		}

		const int leftValue = getValue(from, to, k * 2 + 1, l, (l+r) / 2),
				rightValue = getValue(from, to, k * 2 + 2, (l+r) / 2, r);
		return max(leftValue, rightValue) + datas[k].add;
	}

	int getValue(int from, int to) {
		return getValue(from, to, 0, 0, size);
	}

	int addRange(int from, int to, int k, int l, int r, int add){
		
		if (r <= from || to <= l) {
			return datas[k].maxi + datas[k].add;
		}
		
		if (from <= l && r <= to) {
			datas[k].add += add;
			return datas[k].maxi + datas[k].add;
		}

		const int leftValue = addRange(from, to, k * 2 + 1, l, (l+r) / 2, add),
				rightValue = addRange(from, to, k * 2 + 2, (l+r) / 2, r, add);
		datas[k].maxi = max(leftValue, rightValue);
		return datas[k].maxi + datas[k].add;
	}

	void addRange(int from, int to, int value) {
		addRange(from, to, 0, 0, size, value);
	}
};

SegmentTree stree;

const int MAX_N = int(1e4);
int N, W, H;
int xs[MAX_N], ys[MAX_N], as[MAX_N];
int numX[2*MAX_N], numY[2*MAX_N];
int X, Y;
vector< pair<int, int> > add[2*MAX_N], rem[2*MAX_N];

bool init() {
	if (scanf("%d%d%d", &N, &W, &H) == EOF) {
		return false;
	}
	for (int i = 0; i < N; ++i) {
		scanf("%d%d%d", xs+i, ys+i, as+i);
		xs[i] -= 10000000;
		ys[i] -= 10000000;
	}
	for (int i = 0; i < 2*N; ++i) {
		add[i].clear();
		rem[i].clear();
	}
	return true;
}

int solve() {
	for (int i = 0; i < N; ++i) {
		numX[2*i+0] = xs[i];
		numX[2*i+1] = xs[i] + W;
		numY[2*i+0] = ys[i];
		numY[2*i+1] = ys[i] + H;
	}
	sort(numX, numX + 2*N);
	X = unique(numX, numX + 2*N) - numX;
	sort(numY, numY + 2*N);
	Y = unique(numY, numY + 2*N) - numY;

	for (int i = 0; i < N; ++i) {
		int p = lower_bound(numX, numX + X, xs[i]) - numX;
		add[p].push_back(make_pair(ys[i], as[i]));
	}

	for (int i = 0; i < N; ++i) {
		int p = lower_bound(numX, numX + X, xs[i] + W) - numX;
		rem[p].push_back(make_pair(ys[i], as[i]));
	}

	stree.init(Y);
	int ans = 0;
	for (int i = 0; i < X; ++i) {
		
		for (int j = 0; j < int(add[i].size()); ++j) {
			int start = lower_bound(numY, numY + Y, add[i][j].first) - numY;
			int end = lower_bound(numY, numY + Y, add[i][j].first + H) - numY;
			stree.addRange(start, end, add[i][j].second);
		}

		
		for (int j = 0; j < int(rem[i].size()); ++j) {
			int start = lower_bound(numY, numY + Y, rem[i][j].first) - numY;
			int end = lower_bound(numY, numY + Y, rem[i][j].first + H) - numY;
			stree.addRange(start, end, -rem[i][j].second);
		}

		
		for (int j = 0; j < int(add[i].size()); ++j) {
			int start = lower_bound(numY, numY + Y, add[i][j].first) - numY;
			int end = lower_bound(numY, numY + Y, add[i][j].first + H) - numY;
			updateMax(ans, stree.getValue(start, end));
		}
	}

	return ans;
}

int main() {
	for (;init();) {
		printf("%d\n", solve());
	}
	return 0;
}