Stars in Your Window

题意：
在一个天空中有颗星星(看作平面直角坐标系)，已知每颗星星的坐标和亮度(都是整数)。求用宽为、高为的矩形(都是整数)能圈住的星星的亮度总和最大是多少(矩形边界上的星星不算)。 ，应该是不大于的

思路：

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

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

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

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

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

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