J 能到达吗 题解

你有一个 的矩阵 定义两个格子联通为四联通

求出所有联通块的 其中 为联通块大小

考虑扫描线

首先找出所有的整个的矩形然后相邻行的合并即可

合并可以用并查集实现

细节比较多不太好写

复杂度

#include <bits/stdc++.h>
#define LL long long
#define int long long
using namespace std;
template <typename T> void read(T &x){
    x = 0; char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0',ch = getchar();
}
const int K = 2000050,N = 200050,P = 1e9 + 7;
int n,m,k;
struct Point{ int x,y; Point(int xx=0,int yy=0){ x=xx,y=yy; } }a[K];
vector<int>G[N];
inline bool cmpxp(Point A,Point B){ return (A.x != B.x) ? (A.x < B.x) : (A.y < B.y); }
int fa[K<<1],size[K<<1];
inline int Find(int x){ return x == fa[x] ? x : fa[x] = Find(fa[x]); }
inline void Merge(int x,int y){ if ((x=Find(x))==(y=Find(y))) return; fa[y] = x,size[x] = (size[x]+size[y])%P; }

struct Mat{ int xl,xr,yl,yr; }ma[K<<1]; int cntid;
inline bool cmpx(Mat A,Mat B){ return (A.xl != B.xl) ? (A.xl < B.xl) : (A.yl < B.yl); }
int vx[K],lv; int vis[N];

int lb,b[N],bl[N],br[N],fl[N],fr[N];
int lc,c[N],cl[N],cr[N];
inline bool check(int l1,int r1,int l2,int r2){ return max(l1,l2) <= min(r1,r2); }
inline void work(int l1,int r1,int l2,int r2){
    int i,j,cll,crr,L,R,Mid;
    lb = r1-l1+1; for (i = l1; i <= r1; ++i) b[i-l1+1] = i;
    lc = r2-l2+1; for (i = l2; i <= r2; ++i) c[i-l2+1] = i;
    for (i = 1; i <= lb; ++i) bl[i] = ma[b[i]].yl,br[i] = ma[b[i]].yr,fl[i] = -1,fr[i] = -2;
    for (i = 1; i <= lc; ++i) cl[i] = ma[c[i]].yl,cr[i] = ma[c[i]].yr;
    for (i = 1; i <= lb; ++i) if (check(bl[i],br[i],cl[1],cr[lc])){
        fl[i] = 1,L = 1,R = lc;
        while (L <= R){
            Mid = L+R>>1; if (cr[Mid] < bl[i]) fl[i] = Mid + 1,L = Mid + 1; else R = Mid - 1;
        }
        L = fl[i],R = lc,fr[i] = fl[i]-1;
        while (L <= R){
            Mid = L+R>>1; if (cl[Mid] <= br[i]) fr[i] = Mid,L = Mid + 1; else R = Mid - 1;
        }
        if (!check(fl[i],fr[i],1,lc)) bl[i] = -1,br[i] = -2;
        else if (!check(bl[i],br[i],cl[fl[i]],cr[fl[i]])) bl[i] = -1,br[i] = -2;
        else if (!check(bl[i],br[i],cl[fr[i]],cr[fr[i]])) bl[i] = -1,br[i] = -2;
        else Merge(b[i],c[fl[i]]);
    }
    int lst = -1,nl = -1,nr = -2;
    for (i = 1; i <= lb; ++i) if (fl[i] <= fr[i]){
        if (lst != -1 && check(nl,nr,fl[i],fr[i])) Merge(lst,b[i]),nr = fr[i];
        else{
            if (lst != -1) for (j = nl; j <= nr; ++j) Merge(lst,c[j]);
            lst = b[i],nl = fl[i],nr = fr[i];
        }
    }
    if (lst != -1) for (i = nl; i <= nr; ++i) Merge(lst,c[i]);
}
inline void solve(){
    int i,j,v,t;
    read(n),read(m),read(k),cntid = 0;
    for (i = 1; i <= k; ++i) read(a[i].x),read(a[i].y);
    sort(a+1,a+k+1,cmpxp);
    vx[lv=1]=0;
    for (i = 1; i <= k; ++i) G[a[i].x].push_back(a[i].y),vx[++lv] = a[i].x,vis[a[i].x] = 0;
    vx[++lv] = n+1;
    sort(vx+1,vx+lv+1);
    cntid = 0;
    for (i = 1; i < lv; ++i) if (vx[i] + 1 < vx[i+1]){
        ++cntid;
        ma[cntid].yl = 1,ma[cntid].yr = m;
        ma[cntid].xl = vx[i]+1,ma[cntid].xr = vx[i+1]-1;
    }
    for (i = 1; i <= k; ++i) if (!vis[a[i].x]){
        t = a[i].x; vis[t] = 1;
        G[t].push_back(0),G[t].push_back(m+1); sort(G[t].begin(),G[t].end());
        for (j = 0; j < G[t].size()-1; ++j) if (G[t][j] + 1 < G[t][j+1]){
            ++cntid;
            ma[cntid].yl = G[t][j]+1,ma[cntid].yr = G[t][j+1]-1;
            ma[cntid].xl = ma[cntid].xr = t;
        }
        G[t].clear();
    }
    sort(ma+1,ma+cntid+1,cmpx);
    for (i = 1; i <= cntid; ++i)
        fa[i] = i,size[i] = 1ll * (ma[i].xr-ma[i].xl+1) * (ma[i].yr-ma[i].yl+1) % P;
    int nl = 1,nr = 1,nxl = ma[1].xl,ll = -1,lr = -1;
    for (i = 2; i <= cntid; ++i){
        if (nxl == ma[i].xl){ nr = i; continue; }
        if (ll != -1 && abs(ma[ll].xr-ma[nl].xl) == 1) work(ll,lr,nl,nr);
        ll = nl,lr = nr; nl = nr = i,nxl = ma[i].xl;
    }
    if (ll != -1 && abs(ma[ll].xr-ma[nl].xl) == 1) work(ll,lr,nl,nr);
    for (i = 1; i <= k; ++i) G[a[i].x].clear(),vis[a[i].x] = 0;
    int ans = 0;
    for (i = 1; i <= cntid; ++i) if (fa[i] == i) ans = (ans + 1ll * size[i] * (size[i]+1)/2 % P) % P;
    cout << (ans+P)%P << '\n';
}

signed main(){ int T; read(T); while (T--) solve(); return 0; }