HDU 6638 Snowy Smile(线段树)

Posted on | Post modified:

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;
}