当前位置: 首页 > 工具软件 > Snowy-Solon > 使用案例 >

2019多校第六场 HDU6638 Snowy Smile(区间最大子段和)

湛宏旷
2023-12-01

链接HDU6638 Snowy Smile

题意:

给出平面直角坐标系上 n ( ≤ 2000 ) n(\le 2000) n(2000)个点 ( x i , y i ) (x_i,y_i) (xi,yi),每个点都有一个权值 w i    ( − 1 0 9 ≤ x i , y i , w i ≤ 1 0 9 ) w_i\;(-10^9\le x_i,y_i,w_i\le10^9) wi(109xi,yi,wi109),选取一个矩形(矩形边分别平行于 x , y x,y x,y轴),使得矩形内及边上所有点的权值之和最大,问最大的权值之和为多少?(允许矩形内及边上不包括任何点)



分析:

因为 n n n的最大只有 2000 2000 2000,所以可以暴力线扫描,先把点全部按 y y y从小到大排序;

我们可以枚举矩形下边界,即 y : y m i n → y m a x y:y_{min}\rarr y_{max} y:yminymax

每次枚举固定了下边界 y 0 y_0 y0,然后上边界 y c u r y_{cur} ycur y 0 y_0 y0一路扫描到 y m a x y_{max} ymax,每次把 y i = y c u r y_i=y_{cur} yi=ycur的点根据其 x i x_i xi w i w_i wi加到 维护区间最大子段和的线段树 中;(即把 y = y c u r y=y_{cur} y=ycur这条线上的点都按照 x i x_i xi加进去)

每次枚举扫描都查询一遍 [ x m i n , x m a x ] [x_{min},x_{max}] [xmin,xmax]内的最大子段和,保存最大值。

要先把 x i , y i x_i,y_i xi,yi离散化,那么就有 x m i n = 1 ,    x m a x = n x ,    y m i n = 1 ,    y m a x = n y x_{min}=1,\;x_{max}=nx,\;y_{min}=1,\;y_{max}=ny xmin=1,xmax=nx,ymin=1,ymax=ny

最终时间复杂度 O ( n 2 log ⁡ n ) O(n^2\log n) O(n2logn)



以下代码:

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=2000+50;
struct point
{
    int x;
    int y;
    LL w;
}p[maxn];
int n,nx,ny,X[maxn],Y[maxn];
void init()
{
    sort(X+1,X+n+1);
    sort(Y+1,Y+n+1);
    nx=unique(X+1,X+n+1)-(X+1);
    ny=unique(Y+1,Y+n+1)-(Y+1);
    for(int i=1;i<=n;i++)
    {
        p[i].x=lower_bound(X+1,X+nx+1,p[i].x)-X;
        p[i].y=lower_bound(Y+1,Y+ny+1,p[i].y)-Y;
    }
}
bool cmp(const point &a,const point &b)
{
    if(a.y!=b.y)
        return a.y<b.y;
    else
        return a.x<b.x;
}
struct node
{
    LL sum;
    LL max_sum;
    LL max_pre;
    LL max_post;
}t[maxn<<2];
void pushup(int rt)
{
    int ls=rt<<1,rs=rt<<1|1;
    t[rt].sum = t[ls].sum+t[rs].sum;
    t[rt].max_sum = max(max(t[ls].max_sum,t[rs].max_sum),t[ls].max_post+t[rs].max_pre);
    t[rt].max_pre = max(t[ls].max_pre,t[ls].sum+t[rs].max_pre);
    t[rt].max_post = max(t[rs].max_post,t[rs].sum+t[ls].max_post);
}
void clr(int rt,int l,int r)
{
    t[rt].max_sum=t[rt].max_pre=t[rt].max_post=t[rt].sum=0;
    if(l==r)
        return;
    int mid=(l+r)>>1;
    clr(rt<<1,l,mid);
    clr(rt<<1|1,mid+1,r);
}
void updata(int rt,int l,int r,int x,LL w)
{
    if(l==r)
    {                                                 //加上w
        t[rt].max_sum=t[rt].max_pre=t[rt].max_post=(t[rt].sum+=w);
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)
        updata(rt<<1,l,mid,x,w);
    else
        updata(rt<<1|1,mid+1,r,x,w);
    pushup(rt);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d %d %lld",&p[i].x,&p[i].y,&p[i].w);
            X[i]=p[i].x;
            Y[i]=p[i].y;
        }
        init();   //离散化
        sort(p+1,p+n+1,cmp);
        LL ans=0;
        int now=1;
        for(int i=1;i<=ny;i++)   //枚举下界y_0
        {
            clr(1,1,nx);
            for(int j=i,k=now;j<=ny;j++)  //扫描遍历上界y_cur
            {
                while(k<=n&&p[k].y==j)    //将y=y_cur的点放入
                {
                    updata(1,1,nx,p[k].x,p[k].w);
                    k++;
                }
                if(j==i)
                    now=k;
                ans=max(ans,t[1].max_sum);  //直接询问根结点的max_sum
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

 类似资料: