扫描线

扫描线(模板)

题意：
求多个矩形的面积并
思路：
对矩形横坐标离散化，一个矩形分为上下两条边，下边记为1，上边记为-1，从下往上扫一个矩形，如果该边为正值说明还没碰到他相应的上边，此时可以记录面积；对记录下的每条边从下往上扫，每次累加剩余长度*两条边的高度差
注意：
一般的扫描线的一个点代表一条线段(防止两条线段端点重合)，因此实际的右边界不是X[t[p].r]而是X[t[p].r+1]

struct scanline{
    ll l,r,h,tag;
    bool operator <(const scanline&tmp)const{
        return h<tmp.h;
    }
} line[M<<1];
struct segmentTree{
    ll l,r,len,tag;
} t[M*8];
ll X[M<<1];
void build(int p,int l,int r){
    t[p].l=l,t[p].r=r,t[p].len=t[p].tag=0;
    if(l==r)return;
    int mid=l+r>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
}
void pushup(int p){
    if(t[p].tag)t[p].len=X[t[p].r+1]-X[t[p].l];
    else if(t[p].l!=t[p].r)t[p].len=t[lson].len+t[rson].len;
    else t[p].len=0;
}
void change(int p,int l,int r,ll d){
    if(X[t[p].r+1]<=l||X[t[p].l]>=r)return;
    if(X[t[p].l]>=l&&X[t[p].r+1]<=r){
        t[p].tag+=d;
        pushup(p);
        return;
    }
    change(lson,l,r,d);
    change(rson,l,r,d);
    pushup(p);
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        ll a,b,c,d;
        cin>>a>>b>>c>>d;
        line[2*i-1]=((scanline){a,c,b,1});
        line[2*i]=((scanline){a,c,d,-1});
        X[2*i-1]=a,X[2*i]=c;
    }
    n*=2;
    sort(line+1,line+n+1);
    sort(X+1,X+n+1);
    ll tot=unique(X+1,X+n+1)-X-1;
    build(1,1,tot-1);
    ll ans=0;
    for(int i=1;i<n;i++){
        change(1,line[i].l,line[i].r,line[i].tag);
        ans+=t[1].len*(line[i+1].h-line[i].h);
    }
    cout<<ans<<'\n';
}

Heidi and the Turing Test (Medium)(扫描线+曼哈顿切尔雪夫)

题意：
给定多个点和整数k，求是否存在一个点，他的曼哈顿距离范围内的包括的点最多
思路：
对于每个点求他的曼哈顿距离范围，可以发现这是个正菱形，可以通过坐标变换转换为求切尔雪夫距离，则该范围为一个正方形，记录对角坐标，扫描重合最多的线段，就变成一个线段树扫描线的板子题了

ll ans;
struct scanline{
    ll l,r,h,tag;
    bool operator <(const scanline&tmp)const{
        if(h!=tmp.h)return h<tmp.h;
        return tag>tmp.tag;
    }
} line[M<<1];
struct segmentTree{
    ll l,r,len,tag,mx;
} t[M<<2];
ll X[M<<1];
void build(int p,int l,int r){
    t[p].l=l,t[p].r=r,t[p].len=t[p].tag=0;
    if(l==r)return;
    int mid=l+r>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
}
void add(int p,int d){
    t[p].tag+=d;
    t[p].mx+=d;
}
void pushup(int p){
    t[p].mx=max(t[lson].mx,t[rson].mx);
}
void pushdown(int p){
    add(lson,t[p].tag);
    add(rson,t[p].tag);
    t[p].tag=0;
}
void change(int p,int l,int r,ll d){
    if(l<=X[t[p].l]&&r>=X[t[p].r]){
        add(p,d);
        return;
    }
    pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=X[mid])change(lson,l,r,d);
    if(r>X[mid])change(rson,l,r,d);
    pushup(p);
}
void solve(){
    int n,r;
    cin>>n>>r;
    for(int i=1;i<=n;i++){
        ll x,y;
        cin>>x>>y;
        ll xx=x+y,yy=x-y;
        ll a=xx-r,b=yy-r,c=xx+r,d=yy+r;
        line[2*i-1]=(scanline){a,c,b,1};
        line[2*i]=(scanline){a,c,d,-1};
        X[2*i-1]=a,X[2*i]=c;
    }
    n*=2;
    sort(line+1,line+n+1);
    sort(X+1,X+n+1);
    int tot=unique(X+1,X+n+1)-X-1;
    build(1,1,tot);
    for(int i=1;i<=n;i++){
        change(1,line[i].l,line[i].r,line[i].tag);
        ans=max(ans,t[1].mx);
    }
    cout<<ans<<"\n";
}