题目背景

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

题目描述

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

输入输出格式

输入格式：

 

本题有多组数据，第一行为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： 

23 5 41 2 32 3 26 3 13 5 41 2 32 3 25 3 1

输出样例#1： 

56

说明

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

 

题解：扫描线哗啦啦来扫~再加上板子即可

// luogu-judger-enable-o2#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           typedef long long ll;using namespace std;int n,ans,p,h,w,t,x,y,l,m;ll b[80005],c[80005];struct point{ int x; int y1; int y2; int l;//闪亮度 }a[80005];struct tree{ int val;//价值 int lazy;//懒标记 }tr[80005];int get(int x){ return lower_bound(c+1,c+1+p,x)-c; //对于给定的已经排好序的c，x最早能插入到那个位置 }void pushdown(int node,int l,int r){ if(tr[node].lazy){ tr[node*2].val+=tr[node].lazy;//左儿子价值++ tr[node*2+1].val+=tr[node].lazy;//右儿子价值++ tr[node*2].lazy+=tr[node].lazy;//左儿子记上懒标记 tr[node*2+1].lazy+=tr[node].lazy;//右儿子记上懒标记 tr[node].lazy=0;//此点清零 }}void change(int node,int l,int r,int l1,int r1,int k){ if(l>r1||r
           
            =r){ tr[node].val+=k; tr[node].lazy+=k; return; } pushdown(node,l,r); int mid=(l+r)/2; change(node*2,l,mid,l1,r1,k); change(node*2+1,mid+1,r,l1,r1,k); tr[node].val=max(tr[node*2].val,tr[node*2+1].val);}int cmp(point x1,point x2){ if(x1.x!=x2.x) return x1.x
            
             x2.l;}int main(){ //freopen("xx.in","r",stdin); //freopen("xx.out","w",stdout); int t; cin>>t; while(t--){ ans=0; m=0; p=0; memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); memset(tr,0,sizeof(tr)); scanf("%d%d%d",&n,&w,&h); for(int i=1;i<=n;i++) { scanf("%d %d %d",&x,&y,&l); a[i].x=x;//横坐标 a[i+n].x=x+w-1;//向右的一条扫描线 a[i].y1=a[i+n].y1=y;//纵坐标 a[i].y2=a[i+n].y2=y+h-1; a[i].l=l;//闪亮度 a[i+n].l=-l;//方便删除（离开扫描线） b[++m]=y; b[++m]=y+h-1; } sort(b+1,b+m+1);//升序排列 for(int i=1;i<=m;i++) if(i==1||b[i]!=b[i-1]) c[++p]=b[i]; n*=2; for(int i=1;i<=n;i++){ a[i].y1=get(a[i].y1); a[i].y2=get(a[i].y2); } sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++){ change(1,1,p,a[i].y1,a[i].y2,a[i].l); ans=max(ans,tr[1].val); } printf("%d\n",ans); } return 0;}