该题和 黑书 P102 采矿 类似
参考链接：
http://blog.csdn.net/shiqi_614/article/details/7819232
http://blog.csdn.net/tsaid/article/details/6686907
http://www.cnblogs.com/372465774y/archive/2012/07/28/2613272.html
题意：
给你10000以内的星星的坐标和星星的亮度（即分别为x,y,c），要求用W*H的矩形去围住一个区域，
使得这个区域内的星星的亮度最大，并且要求矩形边框上的星星不计入内。矩形可以平移，但不能旋转。
思路：
这题我觉得的精妙之处就是将点转化成矩形，即对每一颗星星，画出以它为左下角的矩形，这个矩形就是它的影响范围。
另外有一点需要注意，题目要求不包括矩形边上的点。
但其实矩形下边（即y）和矩形左边（即x）这两边的星星可以算入进去，
而矩形上边（即y+h）和矩形右边（即x+w）这两边的星星不能被算入。
原因是只要把矩形往左下角移动那么一点点，就把下边和左边上的星星给包括进去了。
因此一颗星星(x,y)，它所能影响到的矩形的横轴区间为[x,x+w-1]，纵轴区间为[y,y+h-1]
所以为了方便处理，我们将每一颗星建立两条线line1(x,y,y+h-1,c),line2(x+w,y,y+h-1,-c)
这样当我们不断插入星星的时候，其实就相当于有一个矩形框在从左往右移动，因为碰到 line1 则对应的影响区间[y,y+h-1]总亮度加上c，说明矩形中包含了该星星。
碰到 line2 则再加上 -c， 那么 c + (-c ) = 0， 相当于该星星已不在矩形框内。
那么，我们每插入一颗星就得到一个 宽度范围 固定（即w），但是 高度范围 不定（即h）的矩形。
如此便只需要维护 y 坐标这一个变量了，让 [y,y+h-1] 这一区间加上c， 用线段树求得此时刻的最大值。
当所有星星都插入完成，得到的最大值也就是我们要求的值了。
还有一点是，对于排序的时候，若x相同，-c的要先放在前面。因为如果优先+c的边，
那么位于x处的星星就会影响到x+w，而实际它是不能算入的。
最后注意：数据会超int，所以类型要设成long long
第一次写的代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#define lson rt<<1,L,mid
#define rson rt<<1|1,mid+1,R using namespace std;
const int maxn=;
int n,w,h;
long long x,y,val;
long long yy[maxn]; //存储纵坐标的值
int idx; //yy数组的下标
map<long long,int> hashy; //纵坐标y的映射
int cnt; //离散值 struct Line{
long long x,y1,y2; //y1=y,y2=y+h-1
long long c; //亮度
//按照x从小到大排序，若x相同，则c小的(即-c)排在前面
bool operator<(const Line tmp)const{
if(x==tmp.x)
return c<tmp.c;
else
return x<tmp.x;
}
}line[maxn]; struct Node{
long long sum; //存储该区间中的最大值
long long add;
}tree[maxn<<]; void build(int rt,int L,int R){
tree[rt].sum=tree[rt].add=;
if(L==R)
return;
int mid=(L+R)>>;
build(lson);
build(rson);
}
void pushUp(int rt){
tree[rt].sum=max(tree[rt<<].sum,tree[rt<<|].sum);
}
void pushDown(int rt){
if(tree[rt].add){
tree[rt<<].add+=tree[rt].add;
tree[rt<<|].add+=tree[rt].add;
tree[rt<<].sum+=tree[rt].add;
tree[rt<<|].sum+=tree[rt].add;
tree[rt].add=;
}
}
void update(int rt,int L,int R,int l,int r,long long c){
if(l<=L&&R<=r){
tree[rt].sum+=c;
tree[rt].add+=c;
return;
}
pushDown(rt);
int mid=(L+R)>>;
if(l<=mid)
update(lson,l,r,c);
if(r>mid)
update(rson,l,r,c);
pushUp(rt);
} int main()
{
while(scanf("%d%d%d",&n,&w,&h)!=EOF){
idx=-;
for(int i=;i<=n;i++){
scanf("%I64d%I64d%I64d",&x,&y,&val);
line[*i-].x=x;line[*i-].y1=y;line[*i-].y2=y+h-;line[*i-].c=val;
line[*i].x=x+w;line[*i].y1=y;line[*i].y2=y+h-;line[*i].c=-val;
yy[++idx]=y;
yy[++idx]=y+h-;
}
sort(yy,yy+idx+);
//对y进行离散化
cnt=;
hashy[yy[]]=++cnt;
for(int i=;i<=idx;i++){
if(yy[i]!=yy[i-])
hashy[yy[i]]=++cnt;
}
n*=;
sort(line+,line+n+);
long long ans=;
build(,,cnt);
//将星星一颗一颗地插入
for(int i=;i<=n;i++){
update(,,cnt,hashy[line[i].y1],hashy[line[i].y2],line[i].c);
ans=max(tree[].sum,ans);
}
printf("%I64d\n",ans); }
return ;
}
后来又重写了一遍，没用map，用的是离散化+二分查找离散值
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define lson rt<<1,L,mid
#define rson rt<<1|1,mid+1,R
using namespace std;
const int maxn=+;
int n,w,h;
int cnty,idy;
long long hashy[maxn<<]; struct Line{
long long x,y1,y2;
int c;
bool operator<(const Line tmp)const{
if(x==tmp.x){
return c<tmp.c;
}
else{
return x<tmp.x;
}
}
}line[maxn<<]; struct Node{
long long sum;
long long add;
}tree[maxn<<]; void build(int rt,int L,int R){
tree[rt].sum=tree[rt].add=;
if(L==R)
return;
int mid=(L+R)>>;
build(lson);
build(rson);
}
void pushUp(int rt){
tree[rt].sum=max(tree[rt<<].sum,tree[rt<<|].sum);
}
void pushDown(int rt){
if(tree[rt].add){
tree[rt<<].add+=tree[rt].add;
tree[rt<<|].add+=tree[rt].add;
tree[rt<<].sum+=tree[rt].add;
tree[rt<<|].sum+=tree[rt].add;
tree[rt].add=;
}
} void update(int rt,int L,int R,int l,int r,int c){
if(l<=L&&R<=r){
tree[rt].add+=c;
tree[rt].sum+=c;
return;
}
pushDown(rt);
int mid=(L+R)>>;
if(l<=mid)
update(lson,l,r,c);
if(r>mid)
update(rson,l,r,c);
pushUp(rt);
}
int binarySearch(long long x){
int l=,r=idy+,mid;
while(r-l>){
mid=(l+r)>>;
if(hashy[mid]<=x)
l=mid;
else
r=mid;
}
return l;
}
int main()
{
long long x,y,c;
while(scanf("%d%d%d",&n,&w,&h)!=EOF){
cnty=;
for(int i=;i<=n;i++){
scanf("%lld%lld%lld",&x,&y,&c);
line[*i-].x=x;line[*i-].y1=y;line[*i-].y2=y+h-;line[*i-].c=c;
line[*i].x=x+w;line[*i].y1=y;line[*i].y2=y+h-;line[*i].c=-c;
hashy[cnty++]=y;
hashy[cnty++]=y+h-;
}
n=n*;
sort(hashy+,hashy+cnty);
idy=;
for(int i=;i<cnty;i++){
if(hashy[i]!=hashy[i-])
hashy[++idy]=hashy[i];
}
sort(line+,line+n+);
build(,,idy);
long long ans=;
int a,b;
for(int i=;i<=n;i++){
a=binarySearch(line[i].y1);
b=binarySearch(line[i].y2);
update(,,idy,a,b,line[i].c);
ans=max(tree[].sum,ans);
}
printf("%I64d\n",ans);
}
return ;
}