前置芝士：扫~描~线~

这个题其实还有个清流的背景

尝试解决问题：

我们已知了窗子的长W和宽H，只需要确定矩形的右上角M，整个窗子的位置就确定了。

对于任意的一颗星星 （x，y），我们考虑M放在哪些区域可以得到她。

因为星星的坐标是整数，我们也令M是整数。

注意题目要求：边界不能放。所以，范围就出来了：

左下角$(x,y)$,右上角$(x+W-1,Y+H-1)$。(包括边界)

此时，问题转化成了：平面上有若干个区域，每个区域都带有一个权值，求在哪个坐标上重叠的区域权值和最大。

成功转化成了熟悉的扫~描~线问题。

套路：

取出每个星星形成的矩形，记做四元组。

左边：$(x,y,y+H,k)$。

右边：$(x+W,y,y+H,-k)$。

k是星星的亮度。

然后以x为关键元，对四元组进行排序。

新的问题：x相等怎么办？

答案：右边界优先。

为什么呢？如果这里同时有一个左边界和一个右边界，右边界已经失效了，要先从扫描线中删除。（前面提到，有效范围是x~x+W-1）。

解决了问题，继续进行套路：

对纵坐标进行离散化，得到tot个代表数，这条扫描线就被分成了tot-1段。

用 c[i] 来维护这条扫描线，我们要得到扫描线上的最大值。因此，c[i] 表示扫描线上第 $i$ 段的权值。

走流程：

• 遇到一条边，用这条边修改扫描线。
• 扫一遍c数组，找到最大值，更新ans 。

怎么修改扫描线？我们令纵坐标y的代表数为val(y)。

修改扫描线：c[val(y)~val(y+H)-1]都加上k。

因为边界不能放，所以是val(y+H)-1。

线段树维护c数组

每个节点主要是维护最大值dat。注意一下下传延迟标记就行了。

代码：

#include<bits/stdc++.h>
#define R register int
#define ll long long
using namespace std;
const int N=2*1e4+5;
int n,nn,t;
ll H,W,ans;
struct node{
    ll x,u,v,w;//u,v纵坐标
}da[N];//四元组 
struct aaa{
    ll dat,add;//最大值，懒标记 
}tree[4*N];
ll row[N],tot;//离散化 

ll in(){
    ll x=0;char ch=getchar();
    while(ch>'9'||ch<'0') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}

bool cmp(node a,node b){//四元组排序
    if(a.x==b.x) return a.w<b.w;//重点，右边界优先 
    return a.x<b.x;
}

void reset(){//预处理，清零
    ans=0;tot=0;
    memset(da,0,sizeof(da));
    memset(row,0,sizeof(row));
    memset(tree,0,sizeof(tree));
    return;
}

void scan(){//读入
    n=in();W=in();H=in();
    int a,b,c;nn=n+n;
    for(R i=1;i<=n;i++){
        a=in();b=in();c=in();
        row[i]=b;row[i+n]=b+H;
        da[i].x=a;da[i+n].x=a+W;
        da[i].u=b;da[i+n].u=b;
        da[i].v=b+H;da[i+n].v=b+H;
        da[i].w=c;da[i+n].w=-c;
    }
    return;
}

void row_(){//离散化
    sort(row+1,row+1+nn);
    tot=unique(row+1,row+1+nn)-(row+1);
    return;
}

int query(ll x){//离散化
    return lower_bound(row+1,row+1+tot,x)-row;
}

void spread(int pos){//下传懒标记
    int ls=pos*2,rs=pos*2+1;
    tree[ls].dat+=tree[pos].add;
    tree[rs].dat+=tree[pos].add;
    tree[ls].add+=tree[pos].add;
    tree[rs].add+=tree[pos].add;
    tree[pos].add=0;
    return;
}

void change(int pos,int pl,int pr,int l,int r,ll w){
    if(l<=pl&&r>=pr){
        tree[pos].dat+=w;
        tree[pos].add+=w;
        return;
    }
    if(tree[pos].add) spread(pos);
    int mid=(pl+pr)>>1;
    if(l<=mid) change(pos*2,pl,mid,l,r,w);
    if(r>mid) change(pos*2+1,mid+1,pr,l,r,w);
    tree[pos].dat=max(tree[pos*2].dat,tree[pos*2+1].dat);
    return;
}

int main(){
    t=in();
    while(t--){     
        reset();scan();row_();              
        sort(da+1,da+1+nn,cmp);
        for(int i=1;i<=nn;i++){
            int u=query(da[i].u);
            int v=query(da[i].v)-1;
            change(1,1,tot-1,u,v,da[i].w);
            //懒得建树，将节点的左右端点作为参数传递 
            ans=max(ans,tree[1].dat);
        }
        printf("%lld\n",ans);
    }
    return 0;
}