题目意思很简单,就是你拿一个给定大小的矩形去圈星星,要求你圈到星星最大的亮度是?
这题可以直接二维曲尺解决,因为数据不是很强,但是我们还是讲讲线段树如何解决.还是和上题一样用线段树的扫描线解决,我们把数据做成给定坐标和价值做成扫描线,扫描完了就抛弃,把线段树存节点存成线段,然后我们用add做延迟标记,val做价值.l,r还是和以前一样存可行区间.注意这里我们是查询区间最值!然后就么了.扫描线就是利用线段树可以解决区间问题!这个区间最值一定就是ans了.

#include <bits/stdc++.h>
using namespace std;
const int N=2e4+5;
struct node{
    int l,r,add,val;
}tr[4*N];

struct vv{
    int x,y1,y2,k;
}star[N];

bool cmp(vv a,vv b)
{
    if(a.x==b.x)    return a.k<b.k;
    else            return a.x<b.x;
}
int mp[N*2];//进行离散化.

void spread(int u)//把这个节点的懒标记去除.
{
    tr[u<<1].val+=tr[u].add;
    tr[u<<1|1].val+=tr[u].add;
    tr[u<<1].add+=tr[u].add;
    tr[u<<1|1].add+=tr[u].add;
    tr[u].add=0;
}

void build(int u,int l,int r)//线段树维护的是区间最大值.
{
    if(l==r)
    {
        tr[u]={l,r,0,0};
        return;
    }
    else
    {
        tr[u]={l,r,0,0};
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
    }
}//把tr数组进行线段化

void modify(int u,int l,int r,int x)//更新区间l~r.
{
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        tr[u].val+=x;
        tr[u].add+=x;
        return;
    }
    if(tr[u].add)  spread(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid)  modify(u<<1,l,r,x);
    if(r>mid)   modify(u<<1|1,l,r,x);
    tr[u].val=max(tr[u<<1].val,tr[u<<1|1].val);
}

int main()
{
    int n,w,h;//边界不算..
    while(cin>>n>>w>>h)
    {
        int num=0;
        for(int i=1;i<=n;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            star[++num]={a,b,b+h-1,c};
            mp[num]=b;
            star[++num]={a+w,b,b+h-1,-c};
            mp[num]=b+h-1;//类似奶牛那题.
        }
        sort(mp+1,mp+num+1);
        int m=unique(mp+1,mp+1+num)-mp-1;
        for(int i=1;i<=num;i++)
        {
            star[i].y1=lower_bound(mp+1,mp+1+m,star[i].y1)-mp;
            star[i].y2=lower_bound(mp+1,mp+1+m,star[i].y2)-mp;
        }
        build(1,1,m);
        sort(star+1,star+1+num,cmp);
        int ans=0;
        for(int i=1;i<=num;i++)
        {
            modify(1,star[i].y1,star[i].y2,star[i].k);
            ans=max(ans,tr[1].val);
        }
        printf("%d\n",ans);
    }
    return 0;
}