abcdeffa's Blog

当局者迷，旁观者清。

0%

GMOJ S1495 【宝石】

发表于 更新于

Description

在 $n \times n$ 的地图中有 $m$ 个点，第 $i$ 的点的坐标为 $(x_i, y_i)$，价值为 $c_i$，问你用一个大小为 $k \times k$ 的矩形能框住的点的价值和的最大值是多少。

Solution

考虑将每个点的坐标按横坐标升序排序，横坐标相同的按纵坐标升序排序。对于一个点 $(x_i, y_i)$，右下角在 $[x_i, y] (y \in [y_i, y_i + k])$ 的矩形可以框住它。

于是我们想到开一棵线段树，对于一个点 $(x_i, y_i)$，把横坐标小于 $(x_i - k)$ 的点的贡献都清除掉，然后把线段树下标在 $[y_i, y_i + k]$ 的位置加上一个点权，然后问题就变成了求全局最大值，使用线段树可以轻松解决。

Code

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <cstdio>
#define maxN 60010
struct read{ int x, y, c; } p[maxN];
struct tree{ int max, tag; } a[maxN << 2];
int appear[maxN];
int Min (int x, int y)
{
	return x < y ? x : y;
}
int Max (int x, int y)
{
	return x > y ? x : y;
}
void pushdown (int now, int l, int r)
{
	if(!a[now].tag || l == r)
	{
		return ;
	}
	a[now << 1].max += a[now].tag;
	a[now << 1 | 1].max += a[now].tag;
	a[now << 1].tag += a[now].tag;
	a[now << 1 | 1].tag += a[now].tag;
	a[now].tag = 0;
}
void change (int now, int l, int r, int L, int R, int t)
{
	if(l == L && r == R)
	{
		a[now].max += t;
		a[now].tag += t;
		return ;
	}
	pushdown(now, l, r);
	int mid = (l + r) >> 1;
	if(R <= mid)
	{
		change(now << 1, l, mid, L, R, t);
	}
	else if(mid + 1 <= L)
	{
		change(now << 1 | 1, mid + 1, r, L, R, t);
	}
	else
	{
		change(now << 1, l, mid, L, mid, t);
		change(now << 1 | 1, mid + 1, r, mid + 1, R, t);
	}
	a[now].max = Max(a[now << 1].max, a[now << 1 | 1].max);
}
int query (int now, int l, int r, int L, int R)
{
	if(l == L && r == R)
	{
		return a[now].max;
	}
	pushdown(now, l, r);
	int mid = (l + r) >> 1;
	if(R <= mid)
	{
		return query(now << 1, l, mid, L, R);
	}
	else if(mid + 1 <= L)
	{
		return query(now << 1 | 1, mid + 1, r, L, R);
	}
	else
	{
		int A = query(now << 1, l, mid, L, mid);
		int B = query(now << 1 | 1, mid + 1, r, mid + 1, R);
		return Max(A, B);
	}
}
void px (int l, int r)
{
	int x = l, y = r;
	int mid1 = p[(l + r) >> 1].x, mid2 = p[(l + r) >> 1].y;
	while(x <= y)
	{
		while((p[x].x < mid1) || (p[x].x == mid1 && p[x].y < mid2))
		{
			x++;
		}
		while((p[y].x > mid1) || (p[y].x == mid1 && p[y].y > mid2))
		{
			y--;
		}
		if(x <= y)
		{
			read t = p[x];
			p[x] = p[y];
			p[y] = t;
			x++;
			y--;
		}
	}
	if(l < y)
	{
		px(l, y); 
	}
	if(x < r)
	{
		px(x, r);
	}
}
int main ()
{
	int n = 0, k = 0;
	scanf("%*d %d %d", &n, &k);
	for(int i = 1;i <= n; i++)
	{
		scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].c);
	}
	px(1, n);
	int Ans = 0, tou = 1;
	for(register int i = 1;i <= n; i++)
	{
		change(1, 1, maxN - 10, p[i].y, Min(p[i].y + k, maxN - 10), p[i].c);
		while(p[i].x - p[tou].x > k && tou <= n)
		{
			change(1, 1, maxN - 10, p[tou].y, Min(p[tou].y + k, maxN - 10), -p[tou].c);
			tou++;
		}
		Ans = Max(Ans, query(1, 1, maxN - 10, p[i].y, Min(p[i].y + k, maxN - 10)));
	}
	printf("%d", Ans);
	return 0;
}