题目背景
小卡买到了一套新房子，他十分的高兴，在房间里转来转去。
题目描述
晚上，小卡从阳台望出去，“哇~~~~好多星星啊”，但他还没给其他房间设一个窗户，天真的小卡总是希望能够在晚上能看到最多最亮的星星，但是窗子的大小是固定的，边也必须和地面平行。这时小卡使用了超能力（透视术）知道了墙后面每个星星的位置和亮度，但是小卡发动超能力后就很疲劳，只好拜托你告诉他最多能够有总和多亮的星星能出现在窗口上。
输入输出格式
输入格式：
本题有多组数据，第一行为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个整数，表示每组数据中窗口星星亮度总和的最大值。
输入输出样例
说明
小卡买的窗户框是金属做的，所以在边框上的不算在内。
题解：扫描线哗啦啦来扫~再加上板子即可
// luogu-judger-enable-o2 #include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> 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<l1) return; if(l1<=l&&r1>=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.x; return x1.l>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 ",ans); } return 0; }