题解 P1502 【窗口的星星】

· · 题解

题意大致是给出若干个点以及点的权值，给出一个矩形，求矩形能框住的最大的权值是多少。

我们将双方的角色转换一下，将这些点看做是一个个矩形的左下角的点(x,y)，那么(可以框住这个点的矩形)的右上角点坐标的集合(说集合不太严谨)就可以看做是一个矩形，其右上角为 (x+w,y+h)。

那么问题就转化为给出若干个带权值的矩形，求最大的矩形交。（稍微有点不同，这个不是面积）

题中有说窗户的边缘不能算，为了让所有的矩形区间都是闭的，不妨让矩形上下左右都缩小0.5，同时题中有说所有坐标都是整数，那么+-0.5就没有影响了，所以最终得出的矩形就是一个实边的矩形。 左下角坐标为(x,y),右上角坐标为(x+w-1,y+h-1)

注意到因为一般的扫描线算法中线段树里叶子节点i表示线段[i,i+1],也就是一个[l,r] 的线段在线段树中涵盖的区间是[l,r-1]

这道题主要处理的就是相交情况。而且问题中的点全都是离散的，不存在浮点数，所以最后算下来就变成了一个区间加，区间求最值的问题。

还有一点要注意的是在根据横坐标排序的时候，如果横坐标相同也就是线段重合的时候。注意先加上新的再减去旧的，否则重合的情况就没被算到。

最后上代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define mid ((l+r)>>1)
using namespace std;

const int maxn=1e4+10;
int n,tot,w,h;
int yy[maxn<<1];                    //离散化的y轴 
int rm[maxn<<3],flag[maxn<<3];      //rm表示区间最大值，flag为懒标记 八倍数组，因为2n条线段，线段树要4倍。 
struct seg
{
    int x,y1,y2,c;
    seg(){}
    seg(int xx,int yy1,int yy2,int cc){x=xx,y1=yy1,y2=yy2,c=cc;}
}line[maxn<<1];

bool cmp(const seg &a,const seg &b)//这里注意排序，x相同时先处理入边 
{
    if(a.x==b.x)return a.c>b.c;
    return a.x<b.x;
}
void pushdown(int t,int l,int r)//下传懒标记 
{
    if(flag[t]==0)return;
    rm[t]+=flag[t];
    if(l!=r)        //这里主要防止越界 
    {
        flag[t<<1]+=flag[t];
        flag[t<<1|1]+=flag[t];
    }
    flag[t]=0;
}
void modify(int t,int l,int r,int x,int y,int z)//区间修改 
{
    if(x<=l&&r<=y)
    {
        flag[t]+=z;
        return;
    }
    if(x<=mid)modify(t<<1,l,mid,x,y,z);
    if(y>mid)modify(t<<1|1,mid+1,r,x,y,z);
    pushdown(t<<1,l,mid);
    pushdown(t<<1|1,mid+1,r);
    rm[t]=max(rm[t<<1],rm[t<<1|1]); //回传最值 
}
int main()
{
    int t=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d %d",&n,&w,&h);
        memset(rm,0,sizeof(rm));
        memset(flag,0,sizeof(flag));
        for(int i=1;i<=n;i++)
        {
            int x=0,y=0,c=0;
            scanf("%d %d %d",&x,&y,&c);
            line[i]=seg(x,y,y+h-1,c);
            line[i+n]=seg(x+w-1,y,y+h-1,-c);
            yy[i]=y+h-1;
            yy[i+n]=y;
        }
        n<<=1;//处理的是2n条线段 
        sort(yy+1,yy+1+n);//排序 
        tot=unique(yy+1,yy+1+n)-yy-1;//去重 
        sort(line+1,line+1+n,cmp);//根据横坐标排序 
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            int l=lower_bound(yy+1,yy+1+tot,line[i].y1)-yy;//二分离散化 
            int r=lower_bound(yy+1,yy+1+tot,line[i].y2)-yy;
            modify(1,1,tot,l,r,line[i].c);//修改，这里注意是l和r，一开始我写的r-1竟然对了9个（但实际上是错误的） 
            ans=max(ans,rm[1]);//每次更新最值 
        }
        printf("%d\n",ans);
    }
    return 0;
}

最后告诫自己，具体问题具体分析，本来一开始看到这题直接套了扫描线的板子，后来自己跑了一遍才明白