CF845E Fire in the City(二分+差分)

用二维差分维护哪些点没被覆盖掉，那么最后一个需要覆盖掉这些点

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int N=2e5+10;
const int mod=1e9+7;
int n,m,k;
vector<int> numx,numy;
int m1[1010][1010];
struct node{
    int x,y;
}pos[N];
int find1(int x){
    return lower_bound(numx.begin(),numx.end(),x)-numx.begin()+1;
}
int find2(int x){
    return lower_bound(numy.begin(),numy.end(),x)-numy.begin()+1;
}
bool check(int mid){
    memset(m1,0,sizeof m1);
    numx.clear();
    numy.clear();
    int i,j;
    for(i=1;i<=k;i++){
        numx.push_back(max(1,pos[i].x-mid));
        numx.push_back(min(n+1,pos[i].x+mid+1));
        numy.push_back(max(1,pos[i].y-mid));
        numy.push_back(min(m+1,pos[i].y+mid+1));
    }
    //插入边界线段，因为最后答案可能需要用到边界值减，当然你也可以计算的时候分类讨论
    numx.push_back(n+1);
    numy.push_back(m+1);
    numx.push_back(1);
    numy.push_back(1);
    sort(numx.begin(),numx.end());
    sort(numy.begin(),numy.end());
    numx.erase(unique(numx.begin(),numx.end()),numx.end());
    numy.erase(unique(numy.begin(),numy.end()),numy.end());
    for(i=1;i<=k;i++){
        int pos1=find1(max(1,pos[i].x-mid));
        int pos2=find1(min(n+1,pos[i].x+mid+1));
        int pos3=find2(max(1,pos[i].y-mid));
        int pos4=find2(min(m+1,pos[i].y+mid+1));
        m1[pos1][pos3]++,m1[pos2][pos3]--,m1[pos1][pos4]--,m1[pos2][pos4]++;
    }
    int up=0,down=(int)numx.size();int l=(int)numy.size(),r=0;
    //二维差分矩阵求和，只需枚举到边界-1，因为这就是全部所需空间？
    for(i=1;i<(int)numx.size();i++){
        for(j=1;j<(int)numy.size();j++){
            m1[i][j]+=m1[i-1][j]+m1[i][j-1]-m1[i-1][j-1];
            if(!m1[i][j]){
                up=max(up,i),down=min(down,i);
                l=min(l,j),r=max(r,j);
            }
        }
    }
    if(down==(int)numx.size()||l==(int)numy.size())
        return true;
    down=numx[down-1],up=numx[up]-1;
    l=numy[l-1],r=numy[r]-1;
    if(up-down>2*mid)
        return false;
    if(r-l>2*mid)
        return false;
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++){
        cin>>pos[i].x>>pos[i].y;
    }
    int l=0,r=1e9;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))
            r=mid;
        else
            l=mid+1;
    }
    cout<<l<<endl;
    return 0;
}