题目大意：
给你10000以内的星星的坐标和亮度，让你用一个W × H 的矩形去围住一个区域，使得区域内星星的亮度最大，矩形边缘上的星星不算。
解题思路：
对于每一个星星 建立一个（x， y , y + h , c) 的扫描线 和一个（x + w , y , y + h , - c)的扫描线，将问题转化成求区间最大值。几个需要注意的地方：矩形边缘上的需要处理一下，将每个叶节点设为长度为1的线段。另外此题如果用long long wa掉的话可以改为unsigned.
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#define LL unsigned
#define FOR(i,x,y) for(LL i=x;i<=y;i++)
#define rFor(i,x,y) for(LL i=x;i>=y;i--)
#define lson l , m , rt<<1
#define rson m , r , rt<<1|1
using namespace std;
const LL MAXN = 222222;
LL X[MAXN<<2];
int cnt[MAXN<<2] , MAX[MAXN<<2];
struct Seg
{
LL h , l , r;
int val;
Seg() { }
Seg(LL a , LL b , LL c , int d) : h(a) , l(b) , r(c) , val(d) { }
bool operator < (const Seg& rhs) const
{
return h < rhs.h || (h == rhs.h && val < rhs.val);
}
}ss[MAXN];
void pushdown(int rt)
{
if(cnt[rt])
{
cnt[rt<<1] += cnt[rt];
cnt[rt<<1|1] += cnt[rt];
MAX[rt<<1] += cnt[rt];
MAX[rt<<1|1] += cnt[rt];
cnt[rt] = 0;
}
}
void pushup(int rt)
{
MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);
}
void build(int l , int r , int rt)
{
MAX[rt] = 0 ; cnt[rt] = 0;
if(l + 1 == r) return ;
int m = (l + r) >> 1;
build(lson);
build(rson);
}
void update(int L , int R , int val , int l , int r , int rt)
{
if(L <= l && R >= r)
{
cnt[rt] += val;
MAX[rt] += val;
return ;
}
pushdown(rt);
int m = (l + r) >> 1;
if(L < m) update(L , R , val , lson);
if(R > m) update(L , R , val , rson);
pushup(rt);
}
int N , W , H;
int main()
{
while(scanf("%d%d%d",&N , &W , &H) != EOF)
{
int m = 0;
while(N--)
{
int x , y ,val;
scanf("%d%d%d",&x,&y,&val);
X[m] = y;
ss[m++] = Seg(x , y , (LL)(y + H) , val);
X[m] = (LL)(y + H);
ss[m++] = Seg((LL)(x + W) , y , (LL)(y + H) ,-val);
}
sort(X , X + m);
sort(ss , ss + m);
int k = 1;
for(LL i = 1 ; i < m ; i ++)
if(X[i] != X[i - 1]) X[k++] = X[i];
memset(cnt , 0 , sizeof(cnt));
memset(MAX , 0 , sizeof(MAX));
build(0 , k - 1 , 1);
int ans = 0;
for(int i = 0 ; i < m; i++)
{
int l = lower_bound(X , X + k , ss[i].l) - X;
int r = lower_bound(X , X + k , ss[i].r) - X ;
update(l , r , ss[i].val , 0 , k - 1 , 1);
ans = max(ans , MAX[1]);
}
printf("%d\n",ans);
}
return 0;
}