题解 P1502 【窗口的星星】
IC_QQQ
2019-05-04 16:33:14
## 前置芝士：扫~描~线~
~~这个题其实还有个清流的背景~~
### 尝试解决问题：
我们已知了窗子的长**W**和宽**H**，只需要确定矩形的右上角**M**，整个窗子的位置就确定了。
对于任意的一颗星星 **（x，y）**，我们考虑**M**放在哪些区域可以得到她。
因为星星的坐标是**整数**，我们也令**M**是整数。
注意题目要求：边界不能放。所以，范围就出来了：
左下角$(x,y)$,右上角$(x+W-1,Y+H-1)$。(包括边界)
此时，问题转化成了：**平面上有若干个区域，每个区域都带有一个权值，求在哪个坐标上重叠的区域权值和最大。**
成功转化成了熟悉的**扫~描~线**问题。
### 套路：
取出每个星星形成的矩形，记做**四元组**。
左边：$(x,y,y+H,k)$。
右边：$(x+W,y,y+H,-k)$。
**k**是星星的亮度。
然后以**x**为关键元，对四元组进行排序。
新的问题：**x**相等怎么办？
答案：**右边界**优先。
为什么呢？如果这里同时有一个左边界和一个右边界，右边界已经失效了，要先从扫描线中删除。（前面提到，有效范围是**x~x+W-1**）。
解决了问题，继续进行套路：
对纵坐标进行离散化，得到**tot**个代表数，这条扫描线就被分成了**tot-1**段。
用 **c[i]** 来维护这条扫描线，我们要得到扫描线上的**最大值**。因此，**c[i]** 表示扫描线上第 $i$ 段的权值。
### 走流程：
+ 遇到一条边，用这条边修改扫描线。
+ 扫一遍**c**数组，找到最大值，更新**ans** 。
怎么修改扫描线？我们令纵坐标**y**的代表数为**val(y)**。
修改扫描线：**c[val(y)~val(y+H)-1]**都加上**k**。
因为边界不能放，所以是**val(y+H)-1**。
### 线段树维护**c**数组
每个节点主要是维护最大值**dat**。注意一下下传延迟标记就行了。
### 代码：
```cpp
#include<bits/stdc++.h>
#define R register int
#define ll long long
using namespace std;
const int N=2*1e4+5;
int n,nn,t;
ll H,W,ans;
struct node{
ll x,u,v,w;//u,v纵坐标
}da[N];//四元组
struct aaa{
ll dat,add;//最大值，懒标记
}tree[4*N];
ll row[N],tot;//离散化
ll in(){
ll x=0;char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
bool cmp(node a,node b){//四元组排序
if(a.x==b.x) return a.w<b.w;//重点，右边界优先
return a.x<b.x;
}
void reset(){//预处理，清零
ans=0;tot=0;
memset(da,0,sizeof(da));
memset(row,0,sizeof(row));
memset(tree,0,sizeof(tree));
return;
}
void scan(){//读入
n=in();W=in();H=in();
int a,b,c;nn=n+n;
for(R i=1;i<=n;i++){
a=in();b=in();c=in();
row[i]=b;row[i+n]=b+H;
da[i].x=a;da[i+n].x=a+W;
da[i].u=b;da[i+n].u=b;
da[i].v=b+H;da[i+n].v=b+H;
da[i].w=c;da[i+n].w=-c;
}
return;
}
void row_(){//离散化
sort(row+1,row+1+nn);
tot=unique(row+1,row+1+nn)-(row+1);
return;
}
int query(ll x){//离散化
return lower_bound(row+1,row+1+tot,x)-row;
}
void spread(int pos){//下传懒标记
int ls=pos*2,rs=pos*2+1;
tree[ls].dat+=tree[pos].add;
tree[rs].dat+=tree[pos].add;
tree[ls].add+=tree[pos].add;
tree[rs].add+=tree[pos].add;
tree[pos].add=0;
return;
}
void change(int pos,int pl,int pr,int l,int r,ll w){
if(l<=pl&&r>=pr){
tree[pos].dat+=w;
tree[pos].add+=w;
return;
}
if(tree[pos].add) spread(pos);
int mid=(pl+pr)>>1;
if(l<=mid) change(pos*2,pl,mid,l,r,w);
if(r>mid) change(pos*2+1,mid+1,pr,l,r,w);
tree[pos].dat=max(tree[pos*2].dat,tree[pos*2+1].dat);
return;
}
int main(){
t=in();
while(t--){
reset();scan();row_();
sort(da+1,da+1+nn,cmp);
for(int i=1;i<=nn;i++){
int u=query(da[i].u);
int v=query(da[i].v)-1;
change(1,1,tot-1,u,v,da[i].w);
//懒得建树，将节点的左右端点作为参数传递
ans=max(ans,tree[1].dat);
}
printf("%lld\n",ans);
}
return 0;
}
```