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

链接：HDU6638 Snowy Smile

题意：

给出平面直角坐标系上$n(\le 2000)$个点$(x_i,y_i)$，每个点都有一个权值$w_i(-10^9\le x_i,y_i,w_i\le 10^9)$，选取一个矩形（矩形边分别平行于$x,y$轴），使得矩形内及边上所有点的权值之和最大，问最大的权值之和为多少？（允许矩形内及边上不包括任何点）

---

分析：

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

我们可以枚举矩形下边界，即$y:y_{min}\to y_{max}$；

每次枚举固定了下边界$y_0$，然后上边界$y_{cur}$从$y_0$一路扫描到$y_{max}$，每次把$y_i=y_{cur}$的点根据其$x_i$把$w_i$加到 维护区间最大子段和的线段树 中；（即把$y=y_{cur}$这条线上的点都按照$x_i$加进去）

每次枚举扫描都查询一遍$[x_{min},x_{max}]$内的最大子段和，保存最大值。

要先把$x_i,y_i$离散化，那么就有$x_{min}=1,x_{max}=nx,y_{min}=1,y_{max}=ny$。

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

---

以下代码：

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