POJ 2482 Stars in Your Window

题目中文翻译：

Description

短暂的时间不会模糊我对你的记忆。自从我第一次见到你以后，真的已经过了4年吗？ 4年前，从我看到你微笑的那一刻起，我仍然清楚地记得，在美丽的珠海校园里，当你走出教室，转过头，柔和的夕阳光照在你美丽的脸颊上时，我知道，我知道我已经迷上你了。然后，经过几个月的观察和撬动，你的恩典和你的智慧，你对生活的态度和对未来的期望都会对我的记忆留下深刻的印象。你是我梦寐以求和我分享余生的迷人阳光女孩。唉，实际上你远远超出了我最疯狂的梦想，我不知道如何弥补你和我之间的鸿沟。所以我什么都没有计划，而是等待，等待一个合适的机会。直到现在 - 毕业的到来，我意识到我是一个白痴，应该创造机会，抓住它而不是等待。

这些日子，我一个接一个地和朋友，室友和同学分手，我依然无法相信挥手后，这些熟悉的面孔很快就会从我们的生活中消失，成为一种回忆。我明天将离开学校。而且你计划飞得很远，追求你的未来并实现你的梦想。如果没有命运和运气，也许我们不会再见面。所以今天晚上，我在你宿舍楼周围闲逛，希望能偶然见到你。但相反，你的外表必须加快我的心跳，而我笨拙的舌头可能无法消化掉一个字。我不记得有多少次通过珠海和广州的宿舍楼，每次都希望看到你出现在阳台上，或者你的轮廓出现在窗户上。我想不起有多少次这个想法出现在我的脑海里：叫她出去吃晚饭或者至少谈一谈。但每一次，考虑到你的卓越和我的共同点，勇气超过勇气的优势驱使我默默离开。

毕业，意味着大学生活的结束，这些光荣，浪漫的岁月的结束。你可爱的微笑是我努力工作的原始动力，而这份不求回报的爱将作为我内心深处的回忆而被封存起来。毕业，也意味着新的生活的开始，在前景光明的道路上的足迹。我真心希望你在海外每天都会很开心，一切都会顺利。同时，我会努力摆脱困境，变得更加复杂。在现实中追求自己的爱与幸福将是我永不褪去的理想。

再见了，我的公主！

如果有一天，某个地方，我们有机会聚集在一起，就像当时的灰头发的男人和女人一样，我希望我们能成为好朋友，分享这种记忆，自豪地重温年轻和欢乐的情绪。如果这个机会永远不会到来，我希望我是天上的星星，在你的窗口闪烁，作为朋友祝福你远离你，每晚陪伴你，分享美梦或者一起噩梦。

现在的问题：假设天空是一个平面。所有的星星都躺在它的位置（x，y）。对于每颗恒星，其等级从1到100，代表其亮度，其中100是最亮的，1是最弱的。该窗口是一个矩形，其边缘平行于x轴或y轴。你的任务是告诉我应该把窗户放在哪里，以最大化窗户内恒星的亮度之和。请注意，在窗口边缘的星星不计数。该窗口可以平移，但不允许旋转。

Input

输入中有几个测试用例。每种情况的第一行包含3个整数：n，W，H，表示矩形窗口的星星数量，水平长度和垂直高度。然后n行，每行3个整数：x，y，c，告诉每个星的位置（x，y）和亮度。没有两颗星星在同一点上。

天空中至少有1颗和至多10000颗星。 1 <= W，H <= 1000000,0 <= x，y <2 ^ 31。

Output

对于每个测试用例，请在一行中输出最大亮度。

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

解题思路：

转载自：https://www.cnblogs.com/fengzhiyuan/p/8037434.html

AC代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 
 6 using namespace std;
 7 
 8 struct kkk {
 9     long long x,y1,k,y2;
10 }f[50010];
11 
12 struct kkk2 {
13     long long l,r,lazy,_max;
14 }f1[200000];
15 
16 long long map[50010];
17 
18 bool cmp(kkk a,kkk b) {
19     if(a.x != b.x)  return a.x < b.x;
20     else return a.k < 0;
21 }
22 
23 void pushup(int p) {
24     f1[p]._max = max(f1[p<<1]._max,f1[p<<1|1]._max) + f1[p].lazy;
25 }
26 
27 void build(long long l,long long r,long long p) {
28     f1[p]._max = f1[p].lazy = 0;
29     f1[p].l = map[l];
30     f1[p].r = map[r];
31     if(l + 1 == r) return ;
32     int mid = (l + r) >> 1;
33     build(l,mid,p * 2);
34     build(mid,r,p * 2 + 1);
35     pushup(p);
36 }
37 
38 void update(long long l1,long long r1,long long k,long long p) {
39     if(f1[p].l >= l1 && f1[p].r <= r1) {
40         f1[p]._max += k;
41         f1[p].lazy += k;
42         return ;
43     }    
44     if(l1 < f1[p<<1].r)
45         update(l1,min(f1[p<<1].r,r1),k,p << 1);
46     if(r1 > f1[p<<1|1].l) 
47         update(max(f1[p<<1|1].l,l1),r1,k,p<<1|1);
48     pushup(p);
49 }
50 
51 int main() {
52     long long n,w,h,x,y,k;
53     while(scanf("%I64d%I64d%I64d",&n,&w,&h) != EOF) {
54         int step = 0,sum = 1;
55         for(int i = 1;i <= n; i++) {
56             scanf("%I64d%I64d%I64d",&x,&y,&k);
57             f[step].x = x;
58             f[step].y1 = y;
59             f[step].y2 = y + h;
60             f[step++].k = k;
61             f[step].x = x + w;
62             f[step].y1 = y;
63             f[step].y2 = y + h;
64             f[step++].k = -k;
65             map[sum++] = y;
66             map[sum++] = y + h;
67         }
68         sort(map + 1,map + sum);
69         sum = unique(map + 1,map + sum) - (map + 1);
70         sort(f,f + step,cmp);
71         build(1,sum,1);
72         long long  maxx = 0;
73         for(int i = 0;i < step; i++) {
74             update(f[i].y1,f[i].y2,f[i].k,1);
75             if(f[i].k > 0) maxx = max(maxx,f1[1]._max);
76         }
77         printf("%I64d
",maxx);
78     }
79     return 0;
80 }
81