POJ 2482 Stars in Your Window（线段树扫描线+最浪漫的题意）

灰太狼 2022-06-10 09:58 139阅读 0赞

Fleeting time does not blur my memory of you. Can it really be 4 years since I first saw you? I still remember, vividly, on the beautiful Zhuhai Campus, 4 years ago, from the moment I saw you smile, as you were walking out of the classroom and turned your head back, with the soft sunset glow shining on your rosy cheek, I knew, I knew that I was already drunk on you. Then, after several months’ observation and prying, your grace and your wisdom, your attitude to life and your aspiration for future were all strongly impressed on my memory. You were the glamorous and sunny girl whom I always dream of to share the rest of my life with. Alas, actually you were far beyond my wildest dreams and I had no idea about how to bridge that gulf between you and me. So I schemed nothing but to wait, to wait for an appropriate opportunity. Till now — the arrival of graduation, I realize I am such an idiot that one should create the opportunity and seize it instead of just waiting.  
  
These days, having parted with friends, roommates and classmates one after another, I still cannot believe the fact that after waving hands, these familiar faces will soon vanish from our life and become no more than a memory. I will move out from school tomorrow. And you are planning to fly far far away, to pursue your future and fulfill your dreams. Perhaps we will not meet each other any more if without fate and luck. So tonight, I was wandering around your dormitory building hoping to meet you there by chance. But contradictorily, your appearance must quicken my heartbeat and my clumsy tongue might be not able to belch out a word. I cannot remember how many times I have passed your dormitory building both in Zhuhai and Guangzhou, and each time aspired to see you appear in the balcony or your silhouette that cast on the window. I cannot remember how many times this idea comes to my mind: call her out to have dinner or at least a conversation. But each time, thinking of your excellence and my commonness, the predominance of timidity over courage drove me leave silently.  
  
Graduation, means the end of life in university, the end of these glorious, romantic years. Your lovely smile which is my original incentive to work hard and this unrequited love will be both sealed as a memory in the deep of my heart and my mind. Graduation, also means a start of new life, a footprint on the way to bright prospect. I truly hope you will be happy everyday abroad and everything goes well. Meanwhile, I will try to get out from puerility and become more sophisticated. To pursue my own love and happiness here in reality will be my ideal I never desert.  
  
Farewell, my princess!  
  
If someday, somewhere, we have a chance to gather, even as gray-haired man and woman, at that time, I hope we can be good friends to share this memory proudly to relight the youthful and joyful emotions. If this chance never comes, I wish I were the stars in the sky and twinkling in your window, to bless you far away, as friends, to accompany you every night, sharing the sweet dreams or going through the nightmares together.  
![fd58b24568a9fde49c72c858b058a509_v_1502518637][]  
Here comes the problem: Assume the sky is a flat plane. All the stars lie on it with a location (x, y). for each star, there is a grade ranging from 1 to 100, representing its brightness, where 100 is the brightest and 1 is the weakest. The window is a rectangle whose edges are parallel to the x-axis or y-axis. Your task is to tell where I should put the window in order to maximize the sum of the brightness of the stars within the window. Note, the stars which are right on the edge of the window does not count. The window can be translated but rotation is not allowed.

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

题解：

本题重点不在于写题，在于题目意思qwq，老夫的少女心

以下是百度的一个大佬翻译的题目，翻译的很好：

你窗前的星星

纵时光飞逝如梭，也我对你的回忆也永不黯然。从第一次见面以来，也许已经有四年之久了。但是，我记得，我清晰地记得，四年前的那一天，那一幕，那一抹阳光，那一弯微笑，它们如同刻刀一般，在我心中留下了如此清晰的印记。

四年前，在美丽的珠海校园，在无意间，我瞥见了你的含笑的背影。命运牵引着我的视线向你而去。你轻轻地跨过班级的大门，当你纤细的手抚过门框的那一刻，你回过了头。一束柔软的阳光毫无拘束地流淌在你玫瑰色的脸颊上。我怔住了，我知道，我清楚地知道，我已经为美丽的你而陶醉。几个月，我不断地观察着，打听着，刺探着，我发现了更多的你。优雅慈悲的你，智慧聪颖的你；积极乐观的你，心怀梦想的你，都在我的内心深处安了家。你希望着，能与你这样的魅力阳光女孩白头偕老。唉，实际上，你离我疯狂的梦想很远，而我也不知如何在隔开你我的海湾上架桥。我什么都没有做，只是等待，等待机遇之神的福祉，直到现在。毕业的钟声已然敲响，我这才从梦境中幡然悔悟，我居然是这样一个蠢货！明明能创造机会并抓住它，我却选择了徒劳的等待！

剩下的日子，掰着手指头都能数的清了。老朋友，舍友，同班同学，一个接着一个与我惜别。放下挥动的手，茫然的我却接受不了残酷的真相。这些每天都能见到的熟悉面庞，就这样从我的人生之中消失，然后除了记忆之外，便什么也不剩了。几天后，我也得离开熟悉的校园。我看见，你正计划着飞过重洋，捕捉未来履行梦想。我突然明白，如果没有机缘，我可能再也见不到你的脸了！那一夜，我在你的宿舍外彷徨着，想借机再见你一面。我很矛盾，如果你一出现，我的心跳变得飞快，我笨拙的舌头一个字也吐不出来怎么办？我匆匆地避过别人的目光，经过你的宿舍楼下，用余光撇着你的窗台，到了路口，又忍不住折回来，不记得这个过程重复了多少次。每一次经过，我都强烈盼望着，能看见你突然出现在阳台上，抑或是看见你的轮廓映在窗前！我也不记得，多少次徒生了这样的想法：大声喊出她的名字，请她一起来共享晚餐，或者至少是说个话？想到你的完美与我的平凡，我的勇气最终败给了胆怯。又一次到了路口，我默默离开了，再也没有回过头。

毕业，意味着大学时光之结束，这充满荣誉与浪漫时代的终结。我清晰地记得，你可爱的微笑是我拼搏的最初动力，这种充满遗憾的爱意，永远地被封存在我的记忆之匣里。毕业，也意味着一段新的征程，人生之途上，清晰的脚印指向着明亮的未来。我无比衷心希望，你在国外的时光能充满幸福与美满！当然了，我也会试着摆脱那些幼稚的想法，变得更加成熟。但是，这种追求真爱，追求真正幸福的希冀，我永远都不会让它随岁月干枯！

再见了！我亲爱的公主！

如果有那么一天，在某个地方，我们有缘再见面。也许我们已经成了两鬓斑白的老妪和老翁。我希望我们在那个时候，能成为好朋友，高高兴兴地分享这段美丽的记忆，那时候，青春的火焰又会被重新点燃，每一个人再次被浸入那愉悦的气氛里。假如我得不到这样的机会，我情愿做一颗明亮星星，在你的窗前闪烁，在遥远的地方祝福着你。我会以一个好朋友的身份，和你共度每一个夜晚，与你分享甜蜜的美梦，陪你穿过无尽的恶魇。

![u_1321697814_4192540840_fm_170_s_29A67C3289FE400B4C79D0CA000050B0_w_393_h_225_img.JPEG][]

那么问题来了，假定天空是一个平面，每个星星都有一个坐标(x,y)，每颗星星都有一个等级从1到100不等，代表它的亮度，其中100是最亮的，1是最弱的。窗户是长方形的，有固定的长和宽，边平行于x轴和y轴。你的任务是告诉我如何摆放窗户，才能获得在窗口内所有星星的亮度总和最大值。注意，边框的星星不算。窗口可以被平移，但不允许旋转。

输入

在输入中有几个测试用例。每一行的第一行包含3个整数：n，w，h，表示星形的数目，矩形窗口的水平长度和垂直高度。然后N行如下，有3个整数分别为：X，Y，C，表示星星位置（x，y）和每个恒星的亮度。没有两颗星星在同一点上。

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

输出

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

PS：

23333问题来了，好了言归正传，题还是要做的，题目意思：

给一堆星星的坐标和星星的亮度，给一个窗口的长和宽，让你求这个窗口最多能看到多亮的星星（注意边框上的不算）

思路：

完全无从下手，还以为是什么单调栈单调队列的题，后来居然搜到了律爷的博客，看懂了qwq，真不愧是上一届俱乐部主席，附上大佬博客：[http://blog.csdn.net/u012965890/article/details/38759385][http_blog.csdn.net_u012965890_article_details_38759385]

然后我讲解一下我的理解：

就是把这个问题转化为一个扫描线的问题，我们可以对每一颗星星建两条边，假设星星的坐标x,y，窗口长h，宽w，第一条边就是起点x，终点x+w，高度为y，然后值为亮度的大小第，二条边起始点也一样，只是高度不同为h+y，亮度为负的亮度的值，这两条线段就是星星影响的区间（因为窗口的限制），如果不懂的可以画个图，很好理解，扫描线就相当于移动窗口，我们将这些线段按照高度从小到大排一下序，从下到上扫一遍然后区间更新就好了，然后由于本题的数据非常大，一定要用离散化，也就是保存下每条线段的每一个端点然后排序后去重就好了，律爷这里的区间更新很巧妙，更新的时候更新区间里面用加减，更新外面的区间用max取最大值，这样就相当于最大化取亮度高的星星了，还有就是这题所有数据要用long long，不然就是wa，还有提交用g++，c++会莫名其妙一堆错，输出用%I64d

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    #define INF 1008611111
    #define ll long long
    struct node
    {
        int l,r;
        ll tag;
        ll v;
    }t[20005*4];
    ll xx[20005];
    void Build(int l,int r,int k)
    {
        t[k].l=l;
        t[k].r=r;
        t[k].v=0;
        t[k].tag=0;
        if(l==r)
            return;
        int mid=M;
        Build(l,mid,lson);
        Build(mid+1,r,rson);
    }
    void pushup(int k)
    {
        t[k].v=max(t[lson].v,t[rson].v);
    }
    void pushdown(int k)
    {
        if(t[k].tag!=0)
        {
            t[lson].tag+=t[k].tag;
            t[rson].tag+=t[k].tag;
            t[lson].v+=t[k].tag;
            t[rson].v+=t[k].tag;
            t[k].tag=0;
        }
    }
    void update(int l,int r,int k,int v)
    {
        if(l==t[k].l&&t[k].r==r)
        {
            t[k].tag+=v;
            t[k].v+=v;
            return;
        }
        pushdown(k);
        int mid=M;
        if(r<=mid)
            update(l,r,lson,v);
        else if(l>mid)
            update(l,r,rson,v);
        else
        {
            update(l,mid,lson,v);
            update(mid+1,r,rson,v);
        }
        pushup(k);
    }
    struct edge
    {
        ll l,r;
        ll v;
        ll h;
    }a[20005];
    int cmp(edge x,edge y)//根据高度从小到大排序
    {
        if(x.h!=y.h)
            return x.h<y.h;
        return x.v<y.v;
    }
    int main()
    {
        int i,j,k,m,tot,ans;
        ll maxx,w,h,n,x,y,d;
        while(scanf("%lld%lld%lld",&n,&w,&h)!=EOF)
        {
            tot=0;
            for(i=0;i<n;i++)
            {
                scanf("%lld%lld%lld",&x,&y,&d);
                a[tot].l=x;//存边的信息
                a[tot].r=x+w;
                a[tot].h=y;
                a[tot].v=d;
                a[tot+1].l=x;
                a[tot+1].r=x+w;
                a[tot+1].h=y+h;
                a[tot+1].v=-d;
                xx[tot]=x;
                xx[tot+1]=x+w;//存端点用于离散化
                tot+=2;
            }
            sort(xx,xx+tot);//排序后再去重
            sort(a,a+tot,cmp);
            ans=unique(xx,xx+tot)-xx;//去重
            Build(0,ans,1);//去重后建树
            maxx=0;
            for(i=0;i<tot;i++)
            {
                int l=lower_bound(xx,xx+ans,a[i].l)-xx;
                int r=lower_bound(xx,xx+ans,a[i].r)-xx;
                update(l,r-1,1,a[i].v);//注意这里要-1，因为边框不可取
                maxx=max(maxx,t[1].v);
            }
            printf("%I64d\n",maxx);//输出要处理一下
        }
        return 0;
    }

[fd58b24568a9fde49c72c858b058a509_v_1502518637]: https://odzkskevi.qnssl.com/fd58b24568a9fde49c72c858b058a509?v=1502518637
[u_1321697814_4192540840_fm_170_s_29A67C3289FE400B4C79D0CA000050B0_w_393_h_225_img.JPEG]: /images/20220610/85b5cd43b9f44e978caa9efc7f9d87a0.png
[http_blog.csdn.net_u012965890_article_details_38759385]: http://blog.csdn.net/u012965890/article/details/38759385