遇见poj上最浪漫的题目。。题目里图片以上几百词为一篇模板级英文情书。这情感和细腻的文笔深深地打动了我。。不会写情书的童鞋速度进来学习。传送门
题意：坐标系内有n个星星，每个星星都有一个亮度c (1<= c <= 100)，坐标和亮度都已给出。 有一个矩形的窗户（就是个理想化的矩形），四条边与x轴或y轴平行。矩形可以在坐标系内平移，但不可以进行旋转操作。求这个矩形可以框住的星星的亮度之和最大为多少。注意：恰好在边上的星星不算在内。
思路：好吧，这题又是看别人的题解才做出来的，深深自责中。。。思路最主要也是最难想的地方就是，题目中是用矩形框住星星，在实际求解过程中要转化为对于每一颗星星，先找出能框住它的那些矩形（肯定不止一个）在坐标系内能够覆盖的区域。因为矩形可以平移，有无数中情况，但是极限情况就四种，就是星星位于矩形的四个顶点的情况。可以想象出，总区域该是四个矩形构成的一个大矩形。将这个矩形通过某种操作，覆盖上该星星的亮度c。最后的问题就转化为了，求坐标系内覆盖的亮度最大的矩形。这就转化到了用线段树扫描法求矩形面积的问题上了。
但实际解题过程中，只需要考虑星星位于矩形一个顶点时的情况(这里我也有些迷迷糊糊的，我的理解是，对于最后求得的结果，位于四个顶点的情况是等价的。可以想想最后得到的那个矩形里分布着不均匀的星星，可能对于某星星，这个矩形能够通过位于右上角顶点的情况计算出；对于另一个星星，可能就是右下角的情况了，所以从哪个顶点算都一样)，这样处理起来也特别简单。
思路核心部分：题目中给出的矩形窗户的长为w，宽为h。现对于每一个星星（x, y），都想象一个以它为左下角顶点且长为w，宽为h的矩形。由于位于矩形边上的星星不算。因此这颗星星实际可以作用到的范围，x轴方向为[x, x+w)，y轴方向为[y, y+h)。如果通过自下往上的扫描法，可以沿x轴建线段树，使用cover维护x轴区间内覆盖的亮度，使用tmax维护x轴区间内亮度的最大值。当扫描到一颗星星时，就将一条两端点分别为x, x+w-1（之所以减一，是因为线段树每个叶子表示的区间为该点到下一点之间的区间。），纵坐标为y，权值flag为该星星的亮度c的一条边覆盖到x轴上。但线继续朝上扫描时，当扫描到纵坐标为y+h时，该星星的亮度就不再起作用了。因此，对于每一颗星星，在坐标系内我们还要假象一条边，两端点为x, x+w-1，纵坐标为y+h，权值flag为-c。这样当扫描线到了y+h的高度时，将这条边覆盖到x轴上，便将之前的那条边给抵消了！
这样每往x轴上覆盖一条边，通过线段树维护数据，计算出当前x轴上存在的亮度和的最大值（可以肯定，一定存在一个长为w，宽为h的矩形，它框住的星星亮度和为此时计算出的亮度和最大值），若最大值大于ans，则赋值给ans。最后ans即为结果。
后话：因为x，y的坐标大小可达2^31，因此离散化是必须的。还有，x+w的范围可能超2^31，用int会wa，改成long long就ok了。
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #define maxn 22222 5 #define lson l, m, rt << 1 6 #define rson m + 1, r, rt << 1 | 1 7 using namespace std; 8 int cover[maxn<<2], tmax[maxn<<2]; 9 long long x[maxn]; 10 struct seg 11 { 12 long long l, r, h; 13 int flag; 14 seg() {} 15 seg(long long x1,long long x2,long long y,int s) : l(x1), r(x2), h(y), flag(s) {} 16 bool operator < (const seg &cmp) const 17 { 18 if (h == cmp.h) return flag < cmp.flag; 19 return h < cmp.h; 20 } 21 }ss[maxn]; 22 int bin(long long key,int len,long long x[]) 23 { 24 int l = 0, r = len - 1; 25 while (l <= r) 26 { 27 int m = (l + r) >> 1; 28 if (key == x[m]) return m; 29 else if (key < x[m]) r = m - 1; 30 else l = m + 1; 31 } 32 return -1; 33 } 34 void PushDown(int rt) 35 { 36 if (cover[rt] != 0) 37 { 38 cover[rt<<1] += cover[rt]; 39 cover[rt<<1|1] += cover[rt]; 40 tmax[rt<<1] += cover[rt]; 41 tmax[rt<<1|1] += cover[rt]; 42 cover[rt] = 0; 43 } 44 } 45 void PushUp(int rt) 46 { 47 tmax[rt] = max(tmax[rt<<1], tmax[rt<<1|1]); 48 } 49 void update(int L,int R,int c,int l,int r,int rt) 50 { 51 if (L <= l && r <= R) 52 { 53 cover[rt] += c; 54 tmax[rt] += c; 55 return; 56 } 57 PushDown(rt); 58 int m = (l + r) >> 1; 59 if (L <= m) update(L, R, c, lson); 60 if (m < R) update(L, R, c, rson); 61 PushUp(rt); 62 } 63 int main() 64 { 65 int n, w, h; 66 //freopen("data.in", "r", stdin); 67 while (~scanf("%d%d%d",&n,&w,&h)) 68 { 69 int tot = 0; 70 long long xi, y; 71 int c; 72 memset(cover, 0, sizeof(cover)); 73 memset(tmax, 0, sizeof(cover)); 74 for (int i = 0; i < n; i++) 75 { 76 scanf("%lld%lld%d",&xi,&y,&c); 77 x[tot] = xi; 78 ss[tot++] = seg(xi, xi + w, y, c); 79 x[tot] = xi + w; 80 ss[tot++] = seg(xi, xi + w, y + h, -c); 81 } 82 sort(x, x + tot); 83 sort(ss, ss + tot); 84 int k = 1; 85 for (int i = 1; i < tot; i++) 86 if (x[i] != x[i-1]) x[k++] = x[i]; 87 int ans = 0; 88 for (int i = 0; i < tot - 1; i++) 89 { 90 int l = bin(ss[i].l, k, x); 91 int r = bin(ss[i].r, k, x) - 1; 92 if (l <= r) update(l, r, ss[i].flag, 0, k - 1, 1); 93 if (ans < tmax[1]) ans = tmax[1]; 94 } 95 printf("%d ",ans); 96 } 97 return 0; 98 }