POJ 2482 Stars in Your Window(扫描线、线段树)

题意:

$给定N\le 10^4个星星,每个有权值1\le w_i\le 100$
$现有W\times H的矩形,问能严格框住的星星最大权值和是多少$

分析:

$考虑把问题转化一下,先不管严格框住,考虑极限情况,一个星星位于左下角$
$那么就可以得到框住它的矩形是(x, y),(x+w, y+h)了$
$问题就转化成了类似于矩形面积并的问题,不过这里是求最大值$
$之后扫描线一波、线段树区间更新一波就好了$
$对于严格的情况,闭区间,可以把y+h变成y+h-1,w+h变成w+h-1$
$但是扫描线的时候要注意,因为是闭区间了,所以当重合的时候,要先添加再删除$
$当然扫描线每次都要注意这个的。。$
$嘛,只有查询maxv[1],写个标记永久化偷懒不用pushDown$
$时间复杂度O(nlogn)$

$代码:$

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
//
// Created by TaoSama on 2016-08-24
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e4 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
typedef long long LL;
LL x[N], y[N], r[N];
LL maxv[N << 3], addv[N << 3];
void update(int L, int R, int v, int l, int r, int rt) {
if(L <= l && r <= R) {
maxv[rt] += v;
addv[rt] += v;
return ;
}
int m = l + r >> 1;
if(L <= m) update(L, R, v, l, m, rt << 1);
if(R > m) update(L, R, v, m + 1, r, rt << 1 | 1);
maxv[rt] = max(maxv[rt << 1], maxv[rt << 1 | 1]) + addv[rt];
}
int n, w, h;
#define y1 fddsfsdfds
struct Line {
LL x, d, y1, y2;
Line() {}
Line(LL x, LL d, LL y1, LL y2): x(x), d(d), y1(y1), y2(y2) {}
bool operator<(const Line& l) const {
if(x == l.x) return d < l.d;
return x < l.x;
}
};
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
while(scanf("%d%d%d", &n, &w, &h) == 3) {
vector<LL> ys;
for(int i = 1; i <= n; ++i) {
scanf("%lld%lld%lld", x + i, y + i, r + i);
ys.push_back(y[i]);
ys.push_back(y[i] + h - 1);
}
sort(ys.begin(), ys.end());
ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
vector<Line> events;
for(int i = 1; i <= n; ++i) {
LL y1 = lower_bound(ys.begin(), ys.end(), y[i]) - ys.begin() + 1;
LL y2 = lower_bound(ys.begin(), ys.end(), y[i] + h - 1) - ys.begin() + 1;
events.push_back(Line(x[i], -r[i], y1, y2)); //+ first
events.push_back(Line(x[i] + w - 1, r[i], y1, y2));
}
sort(events.begin(), events.end());
memset(maxv, 0, sizeof maxv);
memset(addv, 0, sizeof addv);
LL ans = 0;
for(int i = 0; i < events.size(); ++i) {
Line& e = events[i];
LL d = -e.d, y1 = e.y1, y2 = e.y2;
update(y1, y2, d, 1, ys.size(), 1);
// pr(e.x); pr(d);pr(y1);pr(y2);prln(maxv[1]);
ans = max(ans, maxv[1]);
}
printf("%lld\n", ans);
}
return 0;
}


1. 除非注明,本博文即为原创,转载请注明链接地址
2. 本博文只代表博主当时的观点或结论,请不要恶意攻击
3. 如果本文帮到了您,不妨点一下 下面分享到 按钮,让更多的人看到