HDU 6638 Snowy Smile(线段树)

HDU 6638 Snowy Smile(线段树求区间连续最大和)

题面

题意

平面坐标系有$n$个点,第$i$个点的坐标为$(x_i,y_i)$,每个点有个权值$w_i$,现在你需要寻找一个矩形把某些点圈起来使得他们的权值和最大。

思路

先把各点的纵坐标离散化,然后把所有的点按照横坐标从小到大排序,枚举矩形的左边界,每加入一个新的点,就把它对应纵坐标$y$的权值和$w[y]$更新并更改右边界,当左右边界都确定以后,利用线段树求得纵坐标的最大连续子段和,不断更新答案。复杂度$O(n^2log(n))$,注意每次枚举左边界都需要重新建树。

代码:

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

using namespace std;
const long long N = 10000;
struct node{
long long x,y,w;
}s[N];
bool cmp(node a,node b){
return a.x<b.x;
}
long long yy[N];
long long w[N];
long long L[N<<1],R[N<<1],S[N<<1],MX[N<<1];
void pushup(long long rt){
S[rt]=S[rt<<1]+S[rt<<1|1];
MX[rt]=max(L[rt<<1|1]+R[rt<<1],max(MX[rt<<1],MX[rt<<1|1]));
L[rt]=max(L[rt<<1],L[rt<<1|1]+S[rt<<1]);
R[rt]=max(R[rt<<1|1],R[rt<<1]+S[rt<<1|1]);
}
void bt(long long rt,long long l,long long r){
if(l==r){
L[rt]=R[rt]=S[rt]=MX[rt]=0;return ;
}
long long mid=(l+r)>>1;
bt(rt<<1,l,mid);
bt(rt<<1|1,mid+1,r);
pushup(rt);
}
void update(long long pos,long long x,long long l,long long r,long long rt){
if(l==r){
MX[rt]=L[rt]=R[rt]=max(0LL,x);
S[rt]=x;
return ;
}
long long mid=(l+r)>>1;
if(pos<=mid) update(pos,x,l,mid,rt<<1);
else update(pos,x,mid+1,r,rt<<1|1);
pushup(rt);
}
int main(){
long long T;scanf("%lld",&T);
while(T--){
memset(yy,0,sizeof(yy));
int n;scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld %lld %lld",&s[i].x,&s[i].y,&s[i].w);
yy[i]=s[i].y;
}
sort(yy+1,yy+n+1);
int m=unique(yy+1,yy+n+1)-yy-1;
for(int i=1;i<=n;i++){
s[i].y=lower_bound(yy+1,yy+m+1,s[i].y)-yy;
}
sort(s+1,s+n+1,cmp);
long long ans=0;
for(int i=1;i<=n;i++){//枚举左边界
if(i==1||s[i].x!=s[i-1].x){
bt(1,1,m);
for(int j=1;j<=m;j++) w[j]=0;
for(int j=i;j<=n;j++){//右边界
w[s[j].y]+=s[j].w;
update(s[j].y,w[s[j].y],1,m,1);
if(s[j].x!=s[j+1].x||j==n) ans=max(ans,MX[1]);
}
}
}
printf("%lld\n",ans);
}
return 0;
}