[2019杭电暑期多校训练营(第六场)-E题]Snowy Smile

题目传送门

题目大意为:

给你 $n(1 \leq n \leq 2000)$个宝箱的坐标,每个宝箱都有一个坐标$(x_i,y_i)(-1e9 \leq x_i,y_i \leq 1e9) $ 价值 $w_i(-1e9 \leq w_i \leq 1e9)$,让你构造一个矩形,使得这个矩形中包含的值总和最大,并输出这个值。

这是一个非常好的题目,我们先把点进行离散化,然后就能够将坐标范围缩小到2000,然后就可以利用线段树动态的来求区间最大子段和

将坐标离散化后,开始枚举矩形的左右边界。对每一个左边界,我们依次枚举右边界,将处于左右边界之间的点根据 $y$ 值存入一维线段树,然后对当前状态在线段树上 $log$ 时间查询区间最大子段和(计算上下边界)即可。时间复杂度约为$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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=10000+10;
const int maxm=20000+10;

struct node{
ll x,y,w;
}p[maxn];
ll t,q,n,m,N,a[maxn],b[maxn];
ll pre[maxm],nxt[maxm],s[maxm],tree[maxm];
bool cmp(node i,node j){return i.x<j.x; }
void init(){ N=1; while(N<m) N*=2; }
void build(){
for(int i=0;i<N*2;i++) pre[i]=nxt[i]=s[i]=tree[i]=0;
}
void update(ll k,ll x){
k+=N-1;
s[k]+=x;
if(s[k]>0) pre[k]=nxt[k]=tree[k]=s[k];
else pre[k]=nxt[k]=tree[k]=0;
while(k){
k=(k-1)/2;
s[k]=s[k*2+1]+s[k*2+2];
pre[k]=max(pre[k*2+1],s[k*2+1]+pre[k*2+2]);
nxt[k]=max(nxt[k*2+2],s[k*2+2]+nxt[k*2+1]);
tree[k]=max(max(tree[k*2+1],tree[k*2+2]),nxt[k*2+1]+pre[k*2+2]);
}
}
void solve(){
ll ans=0;
ll i,j,k;
for(i=1;i<=q;i++){
if(i==1 || p[i].x!=p[i-1].x){
build();
for(j=i;j<=q;j=k){
for(k=j;k<=q && p[j].x==p[k].x;k++) update(p[k].y,p[k].w);
ans=max(ans,tree[0]);
}
}
}
printf("%lld\n",ans);
}
int main()
{
scanf("%lld",&t);
while(t--){
scanf("%lld",&q);
for(int i=1;i<=q;i++){
scanf("%lld %lld %lld",&p[i].x,&p[i].y,&p[i].w);
a[i]=p[i].x;b[i]=p[i].y;
}
sort(a+1,a+q+1);n=unique(a+1,a+q+1)-(a+1);
sort(b+1,b+q+1);m=unique(b+1,b+q+1)-(b+1);
for(int i=1;i<=q;i++){
p[i].x=lower_bound(a+1,a+n+1,p[i].x)-a-1;
p[i].y=lower_bound(b+1,b+m+1,p[i].y)-b-1;
}
sort(p+1,p+q+1,cmp);
init();
solve();
}
return 0;
}
感谢您的支持
-------------本文结束感谢您的阅读-------------