Nowcodercontest5278 J 能到达吗

cnblogs界面

分析：暴力并查集统计联通块，但是要把图分成个整齐的矩形，然后考虑相邻的进行合并

分离矩形：

对于每个黑点按照递增排序，把出现黑点的每一行分成段矩形，行宽为1

没有出现黑点的，找到两边最远的空白区域，列宽就是

合并矩形：

得到个矩形之后，可以看到矩形的都是对齐分成几段的，对于每个相邻的，，把所有相邻的合并，可以尺取找相邻，并查集合并

总复杂度就是

const int N=3e6+10,P=1e9+7;

int n,m,k;
struct Point{//黑点
    int x,y;
    bool operator < (const Point __) const {
        return x<__.x || (x==__.x && y<__.y);
    }
}A[N];

struct Rec{// 矩形
    int lx,rx,ly,ry;
}B[N];
int cnt;
int fa[N];
ll sz[N];
int Find(int x){ return fa[x]==x?x:fa[x]=Find(fa[x]); }
void Union(int x,int y) {
    x=Find(x),y=Find(y);
    if(x==y) return;
    sz[x]+=sz[y],fa[y]=x;
}

int L[N],R[N],fc;

int Check(Rec a,Rec b){
    if(a.ly>b.ly) swap(a,b);
    return a.ry>=b.ly;
} // 检测是否相交


int main() {
    rep(kase,1,rd()) {
        n=rd(),m=rd(),k=rd();
        if(!k) {
            ll ans=1ll*n*m%P;
            ans=(ans*(ans-1)/2+ans)%P;
            printf("%lld\n",ans);
            continue;
        }
        rep(i,1,k) A[i].x=rd(),A[i].y=rd();
        sort(A+1,A+k+1),cnt=0;
        if(A[1].x>1) B[++cnt]=(Rec){1,A[1].x-1,1,m};
        rep(i,1,k) {
            int j=i;
            while(j<k && A[j+1].x==A[j].x) ++j;
            if(A[i].y>1) B[++cnt]=(Rec){A[i].x,A[i].x,1,A[i].y-1};
            rep(d,i+1,j) if(A[d].y-1>A[d-1].y+1) B[++cnt]=(Rec){A[i].x,A[i].x,A[d-1].y+1,A[d].y-1};
            if(A[j].y<m) B[++cnt]=(Rec){A[i].x,A[i].x,A[j].y+1,m}; // 切成k+1段
            i=j;
            if(i<k && A[i+1].x>A[i].x+1) B[++cnt]=(Rec){A[i].x+1,A[i+1].x-1,1,m};// 没有出现黑点的位置
        }
        if(A[k].x<n) B[++cnt]=(Rec){A[k].x+1,n,1,m};// 没有

        rep(i,1,cnt) sz[i]=1ll*(B[i].rx-B[i].lx+1)*(B[i].ry-B[i].ly+1),fa[i]=i; // 预处理并查集

        fc=0;
        rep(i,1,cnt) {
            int j=i;
            while(j<cnt && B[j+1].lx==B[j].lx && B[j+1].rx==B[j].rx) ++j;
            L[++fc]=i,R[fc]=j;
            i=j;
        }//每一层的x1,x2切开
        rep(i,1,fc-1) {
            if(B[i].rx<B[i+1].lx-1) continue;
            int p=L[i];
            rep(j,L[i+1],R[i+1]) {
                while(p<R[i] && B[p+1].ry<=B[j].ry) {
                    if(Check(B[j],B[p])) Union(j,p);
                    ++p;
                }
                if(Check(B[j],B[p])) Union(j,p);
                if(p<R[i] && Check(B[j],B[p+1])) Union(j,p+1);
            }
        }//相邻层合并，p是尺取指针
        ll ans=0;
        rep(i,1,cnt) if(Find(i)==i) {
            sz[i]%=P;
            ans=(ans+sz[i]*(sz[i]-1)/2+sz[i])%P;
        }
        ans=(ans%P+P)%P;
        printf("%lld\n",ans);
    }
}