https://codeforces.com/gym/101550/attachments

并查集

做麻烦了，调了好久

比较方便的做法是只支持插点，把一个点作为一个区域加\(1\)，再看是否能够与其他区域合并

我将从未被覆盖的点与被覆盖过的点分开讨论，导致情况太多，难以判断

因此，以后做题要尽量支持较单一的操作，这样简单而不易出错

\(C++ Code:\)

#include<cstdio>
#include<iostream>
#include<algorithm>
#define T(x,y) ((x-1)*m+y)
#define N 1005
#define QQ 20005
using namespace std;
int dic[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int fg[N][N],f[N*N];
bool pd[N*N];
bool vis[N][N];
int n,m,ans=0,rt,q;
struct node
{
    int X1,Y1,X2,Y2;
}Q[QQ];
int A[QQ];
int u[5];
bool bc[N*N];
int GetF(int x)
{
    return (x==f[x])?x:(f[x]=GetF(f[x]));
}
void dfs(int l,int r)
{
    vis[l][r]=true;
    f[T(l,r)]=rt;
    for (int i=0;i<4;i++)
    {
        int nl=l+dic[i][0],nr=r+dic[i][1];
        if (nl<1||nl>n||nr<1||nr>m||vis[nl][nr]||fg[nl][nr])
            continue;
        dfs(nl,nr);
    }
}
int QAQ[5];
void ins(int l,int r)
{
    for (int i=0;i<4;i++)//向四周搜索其他区域
    {
        u[i]=-1;
        int nl=l+dic[i][0],nr=r+dic[i][1];
        if (nl<1||nl>n||nr<1||nr>m||fg[nl][nr])
            continue;
        int x=T(l,r),y=T(nl,nr);
        y=GetF(y);
        u[i]=y;
    }
    int TrF=0;
    int cnt=0,tot=0;
    for (int i=0;i<4;i++)
        if (u[i]!=-1)
        {
            if (!pd[u[i]])
            {
                pd[u[i]]=true;
                cnt++;
                QAQ[cnt]=u[i];
            }
        }
    bc[GetF(T(l,r))]=false;//成为白色点
    if (!cnt)//孤立的点
    {
        ans++;
        return; 
    }
    for (int i=1;i<=cnt;i++)
        if (!bc[QAQ[i]])//(注：没有必要的判断)
            TrF=QAQ[i],tot++;
    if (TrF)//周围有白色区域，合并过去
    {
        ans-=tot-1;
        for (int i=1;i<=cnt;i++)
        {
            pd[QAQ[i]]=false;
            f[QAQ[i]]=TrF;
        }
        f[GetF(T(l,r))]=TrF;
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            f[T(i,j)]=T(i,j);
    for (int i=1;i<=q;i++)
    {
        scanf("%d%d%d%d",&Q[i].X1,&Q[i].Y1,&Q[i].X2,&Q[i].Y2);
        if (Q[i].X1==Q[i].X2)
        {
            for (int j=Q[i].Y1;j<=Q[i].Y2;j++)
                fg[Q[i].X1][j]++;
        } else
        {
            for (int j=Q[i].X1;j<=Q[i].X2;j++)
                fg[j][Q[i].Y1]++;
        }
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (fg[i][j])
                bc[T(i,j)]=true;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (!vis[i][j]&&!fg[i][j])
            {
                rt=T(i,j);
                dfs(i,j);
                ans++;
            }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (!fg[i][j])
                f[T(i,j)]=GetF(T(i,j));
    for (int i=q;i>=1;i--)
    {
        A[i]=ans;
        if (Q[i].X1==Q[i].X2)
        {
            for (int j=Q[i].Y1;j<=Q[i].Y2;j++)
            {
                fg[Q[i].X1][j]--;
                if (!fg[Q[i].X1][j])
                    ins(Q[i].X1,j);
            }
        } else
        {
            for (int j=Q[i].X1;j<=Q[i].X2;j++)
            {
                fg[j][Q[i].Y1]--;
                if (!fg[j][Q[i].Y1])
                    ins(j,Q[i].Y1);
            }
        }
    }
    for (int i=1;i<=q;i++)
        printf("%d\n",A[i]);
    return 0;
}

Gym101550A Artwork

原文：https://www.cnblogs.com/GK0328/p/13387284.html