【POJ 2482】Stars in Your Window

http://poj.org/problem?id=2482

线段树扫描线

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 20003;
int in() {
	int k = 0, fh = 1; char c = getchar();
	for(; c < '0' || c > '9'; c = getchar())
		if (c == '-') fh = -1;
	for(; c >= '0' && c <= '9'; c = getchar())
		k = (k << 3) + (k << 1) + c - '0';
	return k * fh;
}

namespace SegmentTree {
	int ma[N << 2], lazy[N << 2], L, R, c, top;
	void init(int num) {
		top = num;
	}
	void pushdown(int rt, int l, int r) {
		if (lazy[rt]) {
			lazy[rt << 1] += lazy[rt];
			lazy[rt << 1 | 1] += lazy[rt];
			ma[rt << 1] += lazy[rt];
			ma[rt << 1 | 1] += lazy[rt];
			lazy[rt] = 0;
		}
	}
	void pushup(int rt) {
		ma[rt] = max(ma[rt << 1], ma[rt << 1 | 1]);
	}
	void update(int rt, int l, int r) {
		if (L <= l && r <= R) {
			ma[rt] += c;
			lazy[rt] += c; return;
		}
		int mid = (l + r) >> 1;
		pushdown(rt, l, r);
		if (L <= mid) update(rt << 1, l, mid);
		if (R > mid) update(rt << 1 | 1, mid + 1 ,r);
		pushup(rt);
	}
	void cover(int l, int r, int num) {
		L = l; R = r; c = num;
		update(1, 1, top);
	}
	int query() {
		return ma[1];
	}
}

int n, w, h, H[10003], dis[10003], cnt, down[10003];
struct node {
	int x, y, z;
	bool operator < (const node &A) const {
		return x < A.x;
	}
} S[10003];

int main() {
	while (~scanf("%d%d%d", &n, &w, &h)) {
		cnt = 0;
		for(int i = 1; i <= n; ++i) {
			S[i].x = in(); S[i].y = in(); S[i].z = in();
			H[++cnt] = S[i].y;
		}
		sort(H + 1, H + cnt + 1);
		cnt = unique(H + 1, H + cnt + 1) - H;
		for(int i = 1; i <= n; ++i)
			S[i].y = lower_bound(H + 1, H + cnt, S[i].y) - H;
		sort(S + 1, S + n + 1); 
		int head = cnt - 1, tail = 1;
		for(int i = cnt - 1; i >= 1; --i) {
			while (head >= 1 && H[i] - H[head] < h) --head;
			down[i] = head + 1;
		}
		
		SegmentTree::init(cnt - 1);
		
		head = 1; tail = 1;
		while (tail <= n && S[tail].x - S[1].x < w) {
			SegmentTree::cover(down[S[tail].y], S[tail].y, S[tail].z);
			++tail;
		}
		int ans = SegmentTree::query();
		while (head <= n) {
			SegmentTree::cover(down[S[head].y], S[head].y, -S[head].z);
			++head;
			while (head <= n && S[head].x == S[head - 1].x) {
				SegmentTree::cover(down[S[head].y], S[head].y, -S[head].z);
				++head;
			}
			while (tail <= n && S[tail].x - S[head].x < w) {
				SegmentTree::cover(down[S[tail].y], S[tail].y, S[tail].z);
				++tail;
			}
			ans = max(ans, SegmentTree::query());
		}
		printf("%d
", ans);
	}
	
	return 0;
}