Luogu P1502 窗口的星星

pwq

首先,把星星放在窗户角上肯定是最好的,把每个星星看成一个矩形的左上角,问题就转化成了最大矩形面积并。

盗图大师

离线做,把矩形根据左x排序,扫描线从左往右扫,当扫到矩形左边界,$[y_1, y_2]$贡献+c,扫到右边界贡献-c,每次操作维护线段树的最大值。

注意y需要离散化。

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
#include <bits/stdc++.h>

typedef long long LL;
const int N = 2e5 + 233;
int T;
int n, W, H, lsh[N << 1];
LL ans, t[N << 3], tag[N << 3];
struct Star {
int x, y1, y2;
LL l;
friend bool operator <(Star u, Star v) {
return u.x == v.x ? u.l > v.l : u.x < v.x;
}
} s[N << 1];

inline int read() {
int a = 0; char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) a = a * 10 + c - '0', c = getchar();
return a;
}

void pushdown(int p) {
if (!tag[p]) return;
tag[p << 1] += tag[p], tag[p << 1 | 1] += tag[p];
t[p << 1] += tag[p], t[p << 1 | 1] += tag[p];
tag[p] = 0;
}

void modify(int p, int l, int r, int pl, int pr, LL d) {
if (l >= pl && r <= pr) return (void)(tag[p] += d, t[p] += d);
int mid = (l + r) >> 1;
pushdown(p);
if (pl <= mid) modify(p << 1, l, mid, pl, pr, d);
if (pr > mid) modify(p << 1 | 1, mid + 1, r, pl, pr, d);
t[p] = std::max(t[p << 1], t[p << 1 | 1]);
}

signed main() {
T = read();
while (T--) {
memset(t, 0, sizeof(t));
memset(tag, 0, sizeof(tag));
n = read(), W = read(), H = read();
for (int i = 1; i <= n; ++i) {
int x = read(), y = read(), l = read();
s[i] = {x, y, y + H - 1, l};
s[i + n] = {x + W - 1, y, y + H - 1, -l};
lsh[i] = y, lsh[i + n] = y + H - 1;
}
n <<= 1;
std::sort(lsh + 1, lsh + 1 + n);
int qwq = std::unique(lsh + 1, lsh + 1 + n) - lsh - 1;
std::sort(s + 1, s + 1 + n);
for (int i = 1; i <= n; ++i) {
int l = std::lower_bound(lsh + 1, lsh + 1 + qwq, s[i].y1) - lsh;
int r = std::lower_bound(lsh + 1, lsh + 1 + qwq, s[i].y2) - lsh;
modify(1, 1, qwq, l, r, s[i].l);
ans = std::max(ans, t[1]);
}
printf("%lld\n", ans);
ans = 0;
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×