【Luogu P1502】窗口的星星

（复制一下题面好了~）

题目背景

小卡买到了一套新房子，他十分的高兴，在房间里转来转去。

题目描述

晚上，小卡从阳台望出去，“哇~~~~好多星星啊”，但他还没给其他房间设一个窗户，天真的小卡总是希望能够在晚上能看到最多最亮的星星，但是窗子的大小是固定的，边也必须和地面平行。这时小卡使用了超能力（透视术）知道了墙后面每个星星的位置和亮度，但是小卡发动超能力后就很疲劳，只好拜托你告诉他最多能够有总和多亮的星星能出现在窗口上。

输入输出格式

输入格式：

本题有多组数据，第一行为T 表示有T组数据T<=10

对于每组数据

第一行3个整数n，W，H，（n<=10000,1<=W,H<=1000000）表示有n颗星星，窗口宽为W，高为H。

接下来n行，每行三个整数xi，yi，li 表示星星的坐标在（xi，yi），亮度为li。（0<=xi,yi<2^31)

输出格式：

T个整数，表示每组数据中窗口星星亮度总和的最大值。

输入输出样例

输入样例#1：

输出样例#1：

5

6

说明

小卡买的窗户框是金属做的，所以在边框上的不算在内。

喜欢这个题目背景~

这类题目有一个很巧妙的转化，把移动的窗口（面）和星星（点）转成可以覆盖到星星的（面）和窗口的左下角（点）

什么意思呢？（可以结合下面的图片理解）

把每一个星星作为右上角，在它的左下方划出一片窗口大小的区域，表示只要窗口的左下角落在这一片区域里就一定能覆盖到这颗星星。

那么不同星星的重叠部分就代表能同时覆盖这几颗星星了。

（下图中，只要窗口落在阴影部分，就能同时覆盖到三颗星星）

所以这一题的解法就是：

想象一条扫描线从左扫到右边，只要进入了星星的区域，扫描线上这段区间就可以取到这颗星星的值，等过了区域再减去这颗星星的值。

那就可以用线段树来做啦，每次挪动找出区间的最值更新答案就可以了。

看到题目最后的提示:小卡买的窗户框是金属做的，所以在边框上的不算在内。(惊！

边框居然不算，好吧那就只好把范围缩小，到了阴影部分外的那条平行y轴的线就可以把这颗星星的贡献减掉了。（用Windows XP 画的的图，有点丑）

还有，星星的坐标很大，记得离散化。

具体操作细节可以看代码（用了vector来维护坐标上加和减的星星）

（代码虽然很长，但结构还算清晰吧)

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<algorithm>

 #define For(i,a,b) for(int i=a;i<=b;++i)

 #define Pn putchar('\n')

 #define llg long long

 using namespace std;

 const int N=2e4+;

 struct LIS{

     int x,y,id;

 }Lis[N*];

 struct Star{

     int x1,x2,y1,y2;

     llg lgt;

     Star(){

         x1=; x2=; y1=; y2=;

         lgt=;

     }

 }st[N];

 vector<int>ads[N];

 vector<int>mns[N]; 

 int tot=,n,m,W,H,x,y;

 llg tag[N*],mx[N*],ans=;

 void read(int &v){       //读入优化，和输出优化

     v=; bool fg=;

     char c=getchar(); if(c=='-')fg=;

     while(c<''||c>''){c=getchar(); if(c=='-')fg=;}

     while(c>=''&&c<=''){v=v*+c-'',c=getchar();if(c=='-')fg=;}

     if(fg)v=-v;

 }

 void read(llg &v){

     v=; bool fg=;

     char c=getchar(); if(c=='-')fg=;

     while(c<''||c>''){c=getchar(); if(c=='-')fg=;}

     while(c>=''&&c<=''){v=v*+c-'',c=getchar();if(c=='-')fg=;}

     if(fg)v=-v;

 }

 void write(int x){

     if(x>)write(x/);

     int xx=x%;

     putchar(xx+'');

 }

                         //排序

 bool cmpX(const LIS &a,const LIS &b){

     return a.x<b.x;

 }

 bool cmpY(const LIS &a,const LIS &b){

     return a.y<b.y;

 }

                       //线段树操作

 void pDown(int o){

     llg tg=tag[o];  tag[o]=;

     int ls=o<<,rs=o<<|;

     tag[ls]+=tg; tag[rs]+=tg;

     mx[ls]+=tg; mx[rs]+=tg;

 }

 void Ins(int o,int l,int r,int lx,int rx,llg dt){

     if(lx<=l&&rx>=r){

         mx[o]+=dt; tag[o]+=dt;

         return;

     }

     int m=(l+r)>>;

     int ls=o<<,rs=o<<|;

     if(tag[o])pDown(o);

     if(lx<=m)Ins(ls,l,m,lx,rx,dt);

     if(rx>m)Ins(rs,m+,r,lx,rx,dt);

     mx[o]=max(mx[ls],mx[rs]);

 }

 int main(){

     int T; read(T);

     while(T--){

         tot=; ans=;

         memset(tag,,sizeof(tag));

         memset(mx,,sizeof(mx));

         read(n); read(W); read(H);

         For(i,,n){                        //存下星星区域的右上角和左下角

             read(x); read(y); read(st[i].lgt);

             st[i].x1=st[i].x2=st[i].y1=st[i].y2=;

             Lis[++tot].x=x;

             Lis[tot].y=y,Lis[tot].id=i;

             Lis[++tot].x=x+W-;

             Lis[tot].y=y-H+,Lis[tot].id=i;

         }

         Lis[].x=-;

         Lis[].y=-;

         sort(Lis+,Lis+tot+,cmpY);        //分别对X和Y离散化

         int ty=;

         For(i,,tot){

             if(Lis[i].y!=Lis[i-].y)ty++;

             int ID=Lis[i].id;

             if(!st[ID].y2){

                 st[ID].y2=ty;

             }else{

                 st[ID].y1=ty;

             }

         }

         sort(Lis+,Lis+tot+,cmpX);

         int tx=;

         For(i,,tot){

             if(Lis[i].x!=Lis[i-].x)tx++;

             int ID=Lis[i].id;

             if(!st[ID].x1){

                 st[ID].x1=tx;

             }else{

                 st[ID].x2=tx;

             }

         }

         For(i,,tx+){                  //初始化vector

             ads[i].clear();

             mns[i].clear();

         }

         For(i,,n){

             int lx,rx;          //把星星挂到相应的横坐标上

             lx=st[i].x1;        //ads为加， mns为减

             rx=st[i].x2+;

             ads[lx].push_back(i);

             mns[rx].push_back(i);

         }

         For(i,,tx){

             int sz;

             sz=mns[i].size();

             For(j,,sz-){           //先减后加

                 int ID=mns[i][j];

                 int lx,rx;

                 lx=st[ID].y2;

                 rx=st[ID].y1;

                 Ins(,,ty,lx,rx,-st[ID].lgt);

             }

             sz=ads[i].size();

             For(j,,sz-){

                 int ID=ads[i][j];

                 int lx,rx;

                 lx=st[ID].y2;

                 rx=st[ID].y1;

                 Ins(,,ty,lx,rx,st[ID].lgt);

             }

             ans=max(ans,mx[]);

         }

         write(ans); Pn;

     }

     return ;

 }

巴特西

【Luogu P1502】窗口的星星

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章

巴特西

【Luogu P1502】 窗口的星星

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章

【Luogu P1502】窗口的星星