Zb3VyIHRhc2sgaXMgdG8gdGVsbCB3aGVyZSBJIHNob3VsZCBwdXQgdGhlIHdpbmRvdyBpbiBvcmRlciB0byBtYXhpbWl6ZSB0aGUgc3VtIG9mIHRoZSBicmlnaHRuZXNzIG9mIHRoZSBzdGFycyB3aXRoaW4gdGhlIHdpbmRvdy4gTm90ZSwgdGhlIHN0YXJzIHdoaWNoIGFyZSByaWdodCBvbiB0aGUgZWRnZSBvZiB0aGUgd2luZG93IGRvZXMgbm90IGNvdW50LiBUaGUKIHdpbmRvdyBjYW4gYmUgdHJhbnNsYXRlZCBidXQgcm90YXRpb24gaXMgbm90IGFsbG93ZWQuIDxicj4KCjxwIGNsYXNzPQ=="pst">Input
There are several test cases in the input. The first line of each case contains 3 integers: n, W, H, indicating the number of stars, the horizontal length and the vertical height of the rectangle-shaped window. Then n lines follow, with 3 integers each: x, y, c, telling the location (x, y) and the brightness of each star. No two stars are on the same point.
There are at least 1 and at most 10000 stars in the sky. 1<=W，H<=1000000, 0<=x，y<2^31.
Output
For each test case, output the maximum brightness in a single line.
Sample Input
3 5 4
1 2 3
2 3 2
6 3 1
3 5 4
1 2 3
2 3 2
5 3 1
Sample Output
5
6
――――――――――――――――――――――――分割线――――――――――――――――――――――
题目大意：
浪漫的情书。遇见这样的就嫁了吧
给你n颗星星的坐标，给你一个矩形区域，求在这个矩形区域内最大的星星亮度和
思路：
看了结题报告才会的自己完全没思路
看了n篇结题报告
下面搞 二维树状数组解法 和 扫面线+离散解法
//--------------------------------------------------------------------------------------------------------------------------//
要解决这个问题，首先要知道一个东西，就是给出一个一维的数列，怎么找出连续的，小于等于w个的数，它们的和最大。这个问题可以用线段树O(nlogn)地解决，在将一个数a放到x这个位置的同时，放一个相反数-a在x+w的位置，然后求出整个区间的最大和就是答案。注意，应该先插入-a，再插入a。
首先注意到最优解肯定是窗子的右上角（或其他角）在某个星星位置处（这里的在是模糊的在，略微比星星的位置大一点，能包含这个星星就行）。这样就将问题变成离散空间上的问题了。然后问题关键就是将二维问题变成一维问题，先只考虑x轴方向的一维，可以想到一个星星的起到的作用是一条长度为w的线段，然后答案就是找到被最多线段覆盖的某点，就是区间最值问题了。那么再考虑y轴这一维，这一维可以认为是线段的存活时间。那么将星星分成两条线段，一个代表出生，一个代表死亡,然后按照y坐标顺序插入星星（因为在每个y坐标出要么产生一个新的线段，要么减少一个线段，都会改变已有线段树的状态），线段树的作用就是维护一个区间最值。
我觉得类似的问题有林涛论文《线段树的应用》中的例题 “蛇”，也是有类似这种二维变一维，存活时间的思想。
// ------------------------ ――转载
对每个星星构建一个矩形，长度为w，宽度为h，下底边权值为c，上底边权值为-c
离散化横坐标，对高度h从小到大排序
维护最大前缀和
同一条线段前缀和相加，不同线段取最大
区间维护
#include
#include
#include
#include
#define ll long long #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int maxn=22222; using namespace std; ll cnt[maxn<<2],sum[maxn<<2]; ll X[maxn<<1]; struct Seg { ll l,r,h; int s; Seg(){}; Seg(ll a,ll b,ll c,ll d):l(a),r(b),h(c),s(d){}; bool operator<(const Seg&cmp)const{ if(h==cmp.h) return s
>1; if(L<=m) update(L,R,c,lson); if(m