poj 2482 Stars in Your Window

本文从WordPress迁移而来, 查看全部WordPress迁移文章

线段树

扫描从下往上扫,从竖直高度,“进点”,“出点”

本质是枚举了每个点作为矩形的左下标,然后统计一个矩形内的亮度和

但转化为线段树后不是统计和,而是统计区间最大值,这里值得深思

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
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 10010
#define INF 0x3f3f3f
#define LL long long
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)

int n,m;
LL W,H,Hash[2*N],ans;
struct star{
LL x,y,val;
}s[N];
struct SegTree{
int l,r,mid;
LL Max,lazy;
SegTree(){}
SegTree(int __l,int __r){
l = __l; r = __r; mid = (l+r)>>1;
Max = lazy = 0;
}
}t[N<<2];

bool cmp(star p,star q){
return p.y < q.y;
}

int binary(LL key){
int low = 0;
int high = m-1;
while(low <= high){
int mid = (low + high) >> 1;
if(Hash[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return low;
}

void PushDown(int rt){
if(t[rt].lazy == 0) return ;
t[lson(rt)].lazy += t[rt].lazy;
t[rson(rt)].lazy += t[rt].lazy;
t[lson(rt)].Max += t[rt].lazy;
t[rson(rt)].Max += t[rt].lazy;
t[rt].lazy = 0;
}

void PushUp(int rt){
t[rt].Max = max(t[lson(rt)].Max,t[rson(rt)].Max);
}

void build(int rt,int a,int b){
t[rt] = SegTree(a,b);
if(a == b) return ;
int mid = t[rt].mid;
build(lson(rt),a,mid);
build(rson(rt),mid+1,b);
}

void updata(int rt ,int a,int b,LL val){
if(t[rt].l == a && t[rt].r == b){
t[rt].lazy += val;
t[rt].Max += val;
return ;
}
PushDown(rt);
int mid = t[rt].mid;
if(b <= mid)
updata(lson(rt),a,b,val);
else if(a > mid)
updata(rson(rt),a,b,val);
else{
updata(lson(rt),a,mid,val);
updata(rson(rt),mid+1,b,val);
}
PushUp(rt);
}

void Out(int st,int en){
for(int i = st; i < en; i++){
int a = binary(s[i].x);
int b = binary(s[i].x+W) - 1;
updata(1,a,b,-s[i].val);
}
}

void In(int st,int en){
for(int i = st; i < en; i++){
int a = binary(s[i].x);
int b = binary(s[i].x+W) - 1;
updata(1,a,b,s[i].val);
}
}

int main(){
while(scanf("%d%lld%lld",&n,&W,&H)!=EOF){
for(int i = 0; i < n; i++){
scanf("%lld%lld%lld",&s[i].x,&s[i].y,&s[i].val);
Hash[i] = s[i].x;
}
sort(s,s+n,cmp);

m = 0;
sort(Hash,Hash+n);
for(int i = 0; i < n; i++) //排序,去重,离散化
if(i == 0 || Hash[i] != Hash[i-1])
Hash[m++] = Hash[i];

build(1,0,m-1);
int st,en;
ans = 0; st = en = 0;
for(int i = 0; i < n; i++){
if(i && s[i].y == s[i-1].y) continue;
Out(st,i);
st = i;
int low = st;
int high = n-1;
LL lim = s[st].y + H;
while(low <= high){
int mid = (low + high) >> 1;
if(s[mid].y < lim)
low = mid + 1;
else
high = mid - 1;
}
In(en,low);
en = low;
ans = max(ans,t[1].Max);
if(en >= n) break;
}
printf("%lld\n",ans);
}
return 0;
}