扫描线模板

参考博客 题目：P1502 窗口的星星

线段树处理的是线段（一维几何计数）（张昆玮） 线段树就是处理线段上的区间问题 扫描线把矩形转化为线段（二维转一维） 扫描线就是去除一维，使一堆矩形变成一堆线段，最后再使一堆线段合并成一条线段 扫描线一般处理矩形有关的问题

听懂了思想，代码随便看一份都可以 已过洛谷全部测试点

此题是把观测点缩成一个点，而把星星由一个点变成一个活动范围，再用扫描线，看哪个点的星星数最多

扫描线用了差分的思想

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e5+7;    //洛谷给了1e4，实际要开1e5，洛谷题面有误
struct L{
    ll y1,y2,x,w;
}a[N<<1];
ll tr[N<<2],ly[N<<2],zz[N<<1];
int t,n,wi,hi;
bool cmp(L a,L b){
    return a.x !=b.x ?a.x <b.x :a.w>b.w;
}
void pushdown(int p){
    tr[p*2]+=ly[p];
    ly[p*2]+=ly[p];
    tr[p*2+1]+=ly[p];
    ly[p*2+1]+=ly[p];
    ly[p]=0;
}
void add(int p,int l,int r,int x,int y,int w){
    if(x<=l&&r<=y){
        tr[p]+=w;ly[p]+=w;
        return ;
    }
    pushdown(p);
    int mid=(l+r)>>1;
    if(x<=mid) add(p*2,l,mid,x,y,w);
    if(mid+1<=y) add(p*2+1,mid+1,r,x,y,w);
    tr[p]=max(tr[p*2],tr[p*2+1]);
}
int main(){
    cin >> t;
    while(t--){
        memset(ly,0,sizeof ly);
        memset(tr,0,sizeof tr);
        cin >> n >> wi >> hi;
        wi--;hi--;
        for(int i=1;i<=n;++i){
            cin >> a[i].x >> a[i].y1 >> a[i].w ;a[i].y2 =a[i].y1 +hi;
            a[i+n].x=a[i].x+wi;a[i+n].y1=a[i].y1;a[i+n].y2=a[i].y2; 
            //a[i].w =1;
            a[i+n].w =-a[i].w ;
            zz[i]=a[i].y1 ;zz[i+n]=a[i].y2 ;
        }
        n<<=1;
        sort(zz+1,zz+n+1);
        sort(a+1,a+n+1,cmp);
        int cnt=unique(zz+1,zz+n+1)-zz-1;
        for(int i=1;i<=n;++i){
            a[i].y1=lower_bound(zz+1,zz+cnt+1,a[i].y1)-zz;
            a[i].y2=lower_bound(zz+1,zz+cnt+1,a[i].y2)-zz;
        }
        //cout << "kkk\n";
        ll ans=0;
        for(int i=1;i<=n;++i){
            add(1,1,n,a[i].y1,a[i].y2,a[i].w);
            ans=max(ans,tr[1]);
        }
        cout << ans << "\n"; 
    }
    return 0;
}