题目链接：
算法解析：
扫描线是一种求矩形面积并/周长并的好方法。它模拟了这样一个过程：一条平行于x轴的直线，从下往上扫描，每遇到一个矩形的上/下边界，它的横向长度都会改变。这个过程，我们可以计算面积，周长，重合的矩形数量等信息。（图片来自@NCC79601的洛谷题解，侵删）
为了算法的效率，我们用线段树来维护横向长度的信息（也可以包括重合矩形数量）?。注意这里的线段树每个结点都对应一条横向的线段，比如上图，1号结点维护x[1]~x[4]，4号结点维护x[1]~x[2]。一般地，结点[ i, j ]维护线段[ i, j+1 ]的信息。所以进行线段树操作的时候，要注意右端点位置-1。
1.【模板】扫描线 code
#include <bits/stdc++.h>
using namespace std;
#define debug cout<<"!!!"<<endl;
#define int long long
const int N = 1e5+5;
struct line{
int x,y,h,f; //左，右，高度，flag（1或-1）
bool operator<(const line&l){return h<l.h;}
} l[N<<1]; //l数组记录line，上下各一条线，两倍大小
int n,xl,xr,yl,yr,a[N<<1]; //a数组记录横坐标，左右各一条线，两倍大小
int tag[N<<3], sum[N<<3]; //tag值和总长度，2*4=8倍大小
int ans = 0; //总面积，也就是答案
inline void push_up(int p,int l,int r){
//维护线段树中的长度数据（如果有tag，直接就是这段，否则看儿子来更新）
sum[p] = tag[p]?sum[p]:(l==r?0:sum[p<<1]+sum[p<<1|1]);
}
void change(int p,int l,int r,int x,int y,int f){
if(x<=l && r<=y){ //当前区间属于要修改的区间，直接修改并push_up
sum[p] = (tag[p]+=f) ? a[r+1]-a[l] : 0; //注意修改了定义之后，区间长度是x[r+1]-x[l]！！
push_up(p,l,r); return;
}
int mid = l+r>>1;
if(x<=mid) change(p<<1,l,mid,x,y,f);
if(y>mid) change(p<<1|1,mid+1,r,x,y,f);
push_up(p,l,r);
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n;
for(int i=1; i<=n; i++){
cin>>xl>>yl>>xr>>yr;
a[2*i-1]=xl; a[2*i]=xr; //奇数左线，偶数右线
l[2*i-1]={xl,xr,yl,1}; l[2*i]={xl,xr,yr,-1}; //奇数下线，偶数上线
}
sort(a+1,a+2*n+1); sort(l+1,l+2*n+1);
int tot = unique(a+1,a+2*n+1)-a-2; //去重之后，线段数=横坐标数-1
for(int i=1; i<=2*n; i++){ //遍历每一条line
int xl = lower_bound(a+1,a+tot+1,l[i].x)-a;
int xr = lower_bound(a+1,a+tot+1,l[i].y)-a-1; //注意左移一格，例如[1,4]->[1,3]
ans += sum[1]*(l[i].h-l[i-1].h); //面积 += 宽*高（sum[1]表示横向方向总长度）
change(1,1,tot,xl,xr,l[i].f); //修改扫描线长度（特别注意，树的范围是1~tot，不是1~n）
}
cout<<ans;
}然后我们来看一下这道练习题：窗口的星星。
对于每个星星(x,y)，要使得它能被框柱，窗子右上角坐标必须在范围(x,y)~(x+W,y+H)范围内，注意不包含边界。而扫描线维护线上矩形数量也是不含边界的，刚好吻合。另外要注意上下边界问题。因为不能包含边界，所以要先遍历上边，再遍历新的一条下边，否则线上矩形数量会偏大。（这里就影响到line的排序问题，h相同时，f小的是上边，排前面）
2.窗口的星星 code
#include <bits/stdc++.h>
using namespace std;
#define debug cout<<"!!!"<<endl;
const int N = 1e4+5;
struct line{
int x,y,h,f; //左，右，高度，flag
bool operator<(const line&l){return (h==l.h)?f<l.f : h<l.h;}
//为什么h相同时要让val降序排序？因为两个矩形A，B，假如A的上边贴着B的下边，计算是应该先A出去，再B进来，否则就答案计算多了！！！
} l[N<<2]; //l数组记录line，上下各一条线，两倍大小
int t,n,W,H,xl,xr,yl,yr,c,a[N<<1]; //a数组记录横坐标，左右各一条线，两倍大小
int tag[N<<3], add[N<<3]; //线段上最大tag值，懒标，2*4=8倍大小
int ans = 0; //最大tag值
inline void push_down(int p,int l,int r){
if(add[p]==0) return;
tag[p<<1] += add[p];
tag[p<<1|1] += add[p];
add[p<<1] += add[p];
add[p<<1|1] += add[p];
add[p] = 0;
}
void change(int p,int l,int r,int x,int y,int f){
if(x<=l && r<=y) {tag[p]+=f; add[p]+=f; return;}
int mid = l+r>>1;
push_down(p,l,r);
if(x<=mid) change(p<<1,l,mid,x,y,f);
if(y>mid) change(p<<1|1,mid+1,r,x,y,f);
tag[p] = max(tag[p<<1],tag[p<<1|1]);
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>t; while(t--){
ans = 0; //清0
memset(tag,0,sizeof(tag));
memset(add,0,sizeof(add));
cin>>n>>W>>H;
for(int i=1; i<=n; i++){
cin>>xl>>yl>>c; xr=xl+W; yr=yl+H; //星星覆盖范围
a[2*i-1]=xl; a[2*i]=xr;
l[2*i-1]={xl,xr,yl,c}; l[2*i]={xl,xr,yr,-c};
}
sort(a+1,a+2*n+1); sort(l+1,l+2*n+1);
int tot = unique(a+1,a+2*n+1)-a-1;
for(int i=1; i<=2*n; i++){
int xl = lower_bound(a+1,a+tot+1,l[i].x)-a;
int xr = lower_bound(a+1,a+tot+1,l[i].y)-a-1;
ans = max(ans,tag[1]);
change(1,1,tot,xl,xr,l[i].f);
}
cout<<ans<<'\n';
}
}?