Posts Tagged ‘二叉查找树’

POJ 2482 Stars in Your Window

Posted in PKU OJ on 四月 12th, 2010 by 纳米 – Be the first to comment

2010-04-12，阅读、分析题目（话说我只看完了Here comes the problem那一段-.-）
2010-04-12，实现代码，WA，AC

解题报告：
这道题挺有意思的，不过也没啥好说，因为《算法艺术和信息学竞赛》P102-104上有较为详细的解释。我补充三点：
(1) 针对这道题，由于矩形边上的点不能取，所以我们直接对w h减1；
(2) 实现的时候，不必写平衡树，写个静态的二叉树好了（其实是不是多数的题目都可以这样搞个静态的二叉查找树呢？如果是的话就方便很多了）。不过注意，排序的第一关键字是纵坐标，升序；第二关键字是亮度，降序，因为要确保取到最大值；
(3) 2^31-1+1,000,000会爆int，所以使用unsigned。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

#include <stdio.h>
#include <stdlib.h>
 
const int maxn = 20003;
int n, tree_last;
unsigned w, h, data[maxn][4], tree[maxn][4];
 
bool input() {
	if (scanf("%d%u%u", &n, &w, &h) == EOF)
		return false;
	for (int i = 1; i <= n; ++i) {
		scanf("%u%u%u", &data[(i<<1)-1][0], &data[(i<<1)-1][1], &data[(i<<1)-1][2]);
		data[i<<1][0] = data[(i<<1)-1][0];
		data[i<<1][1] = data[(i<<1)-1][1] + h;
		data[i<<1][2] = -data[(i<<1)-1][2];
	}
	n <<= 1;
	--w, --h;
	return true;
}
 
int comp_x(unsigned x[], unsigned y[]) {
	return x[0]!=y[0] ? (x[0]<y[0]?-1:1) : (x[1]==y[1]?0:(x[1]<y[1]?-1:1));
}
 
int comp_y(unsigned x[], unsigned y[]) {
	return x[1]!=y[1] ? (x[1]<y[1]?-1:1) : (x[2]==y[2]?0:(x[2]>y[2]?-1:1));
}
 
int build_tree(int t) {
	int left = t << 1;
	int right = left + 1;
	if (left <= n)
		build_tree(left);
	data[++tree_last][3] = t;
	tree[t][0] = data[tree_last][2];
	tree[t][1] = tree[t][2] = 0;
	tree[t][3] = 0;
	if (right <= n)
		build_tree(right);
	return 0;
}
 
int max(int x, int y) {
	return x > y ? x : y;
}
 
void tree_update(int t) {
	int left = t << 1, right = (t << 1) + 1;
	left = left > n ? 0 : left;
	right = right > n ? 0 : right;
	tree[t][2] = tree[t][1] + tree[left][2] + tree[right][2];
	tree[t][3] = max(tree[left][3], tree[t][2] - tree[right][2]);
	tree[t][3] = max(tree[t][3], tree[t][2] - tree[right][2] + tree[right][3]);
	if (t > 1)
		tree_update(t >> 1);
}
 
void tree_insert(int w) {
	tree[w][1] = tree[w][0];
	tree_update(w);
}
 
void tree_delete(int w) {
	tree[w][1] = 0;
	tree_update(w);
}
 
int work() {
	qsort(data[1], n, sizeof(int) * 4, (int(*) (const void*, const void*)) comp_y);
	tree_last = 0;
	build_tree(1);
	tree[0][0] = tree[0][1] = tree[0][2] = tree[0][3] = 0;
	qsort(data[1], n, sizeof(int) * 4, (int(*) (const void*, const void*)) comp_x);
	int res = 0, line1 = 0, line2 = 0;
	while (line2 < n) {
		do {
			tree_insert(data[++line2][3]);
		} while (data[line2][0] == data[line2+1][0]);
		while (data[line2][0] - data[line1+1][0] > w) {
			tree_delete(data[++line1][3]);
		}
		res = max(res, tree[1][3]);
	}
	return res;
}
 
int main() {
	while (input())
		printf("%d\n", work());
	return 0;
}