Stars in Your Window

题意：
在一个天空中有 $n$ 颗星星(看作平面直角坐标系)，已知每颗星星的坐标和亮度(都是整数)。求用宽为 $w$ 、高为 $h$ 的矩形( $w,h$ 都是整数)能圈住的星星的亮度总和最大是多少(矩形边界上的星星不算)。 $1\leq n\leq 1e4,1\leq w,h\leq 2^{31}-1$ ， $c$ 应该是不大于 $1e9$ 的

思路：

因为矩阵大小固定，所以矩形可以由它的任一顶点确定。我们可以考虑把矩形的右上角顶点放在什么位置，圈住的星星亮度最大。
对一个星星 $(x,y,c)$ ，能圈住它的矩形右上角的顶点范围是：在左下角顶点为 $(x,y)$ ，右上角顶点为 $(x+w,y+h)$ 的矩形内，不包括边界上的点。这里用区域代指这个范围。

“矩形边界上的星星不算”，这个边界需要处理一下。因为星星的坐标都是整数，所以矩形右上角的顶点 $(x-0.1,y-0.1)$ 和 $(x-0.5,y-0.5)$ 和 $(x-0.9,y-0.9)$ 的结果都是一样的，那么我可以区域是：在左下角顶点为 $(x+0.5,y+0.5)$ ，右上角顶点为 $(x+w-0.5,y+h-0.5)$ 的矩形内，包括边界上的点。如果我把星星的坐标往左下移 $0.5$ 呢，那么区域变成：在左下角顶点为 $(x,y)$ ，右上角顶点为 $(x+w-1,y+h-1)$ 的矩形内，包括边界上的点，区域内点的坐标都是整数即可！

此时，问题转化为：平面上有若干个区域，每个区域都带有一个权值，求在那个坐标上重叠的区域权值最大。其中，每一个区域都是由一颗星星产生的，权值等于星星的亮度，把原问题中的矩形右上角放在该区域中就能圈住这颗星星。

问题转化后就可以使用扫描线算法，取每个区域的左右边界，保存成两个四元组 $(x,y,y+h-1,c)$ 和 $(x+m,y,y+h-1,-c)$ 。把这些四元组按照横坐标排序。扫描线就是类似差分的思想，以横坐标为转移，把纵坐标的区间权值并起来。区域的右上角顶点是 $(x+w-1,y+h-1)$ ，而另一个四元组为 $(x+m,y,y+h-1,-c)$ ，就相当于给你一个数组 $a$ ，要在区间 $[L,R]$ 加上值 $c$ ，那么差分的操作就是 $a[L]+=c,a[R]+=c$ ，然后用前缀和就可以得到修改后的数组 $a$ ，而扫描线就相当于一个求前缀和的过程。

将纵坐标的区间权值并起来可以用到线段树，只涉及区间修改，同时维护区间最大值，需要懒标记。
考虑到 $y$ 比较大，但是四元组中的纵坐标最多只有 $2e4$ 个，先离散化。

MyCode:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
using namespace std;
const int maxn=2e4+7,maxE=8e4+7;
typedef long long int ll;
struct node {
    ll x,l,r,val;
    bool operator<(const node& a)const {
        return x<a.x;
    }
} q[maxn];
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
ll lazy[maxE],tree[maxE];
inline ll max(ll a,ll b) {
    return a>b?a:b;
}
inline void pushdown(int rt) {
    if(lazy[rt]) {
        lazy[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        tree[rt<<1]+=lazy[rt];
        tree[rt<<1|1]+=lazy[rt];
        lazy[rt]=0;
    }
}
inline void update(int x,int y,ll val,int l,int r,int rt) {
    if(x<=l&&r<=y) {
        lazy[rt]+=val;
        tree[rt]+=val;
        return;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    if(x<=mid) update(x,y,val,lson);
    if(y>mid) update(x,y,val,rson);
    tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
}
ll b[maxn];
int main() {
    int n,w,h,tot=0;
    while(~scanf("%d%d%d",&n,&w,&h)) {
        tot=0;
        memset(lazy,0,sizeof lazy);
        memset(tree,0,sizeof tree);
        for(ll i=0,x,y,c; i<n; ++i) {
            scanf("%lld%lld%lld",&x,&y,&c);
            q[++tot]=node {x,y,y+h-1,c};
            b[tot]=y;
            q[++tot]=node {x+w,y,y+h-1,-c};
            b[tot]=y+h-1;
        }
        sort(b+1,b+1+tot);
        int mm=unique(b+1,b+1+tot)-b;
        for(int i=1; i<=tot; i+=2) {
            q[i].l=q[i+1].l=lower_bound(b+1,b+mm,q[i].l)-b;
            q[i].r=q[i+1].r=lower_bound(b+1,b+mm,q[i].r)-b;
        }
        sort(q+1,q+1+tot);
        ll ans=0;
        mm-=1;
        for(int i=1; i<=tot; ++i) {
            update(q[i].l,q[i].r,q[i].val,1,mm,1);
            if(q[i].val>0)
                ans=max(ans,tree[1]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}