A - Artwork Gym - 101550A

题意：给你n*m个格子每次添加一条黑线，问这些黑线将白格子分成几个部分。

题解：首先将全部黑线涂上，将每个格子标记在那个块上，对于询问从后往前删除，并将删除之后的白格子赋值为新的块，然后并查集合并，结果就是这次询问的块数。

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
int n,m,p;
struct node{
    int x1,y1,x2,y2;
}s[maxn*10]; int top=0;
int mp[maxn][maxn],vis[maxn][maxn],a[maxn][maxn],b[maxn*maxn];
int zhuan(int i,int j){
    return (i-1)*m+j;
}
void init(){

    for(int i=1;i<=n*m;i++) b[i]=i;
    for(int i=1;i<=p;i++){
        if(s[i].x1==s[i].x2){
            int y1=s[i].y1,y2=s[i].y2;
            for(int j=min(y1,y2);j<=max(y1,y2);j++){
                mp[s[i].x1][j]++;
            }
        }
        else if(s[i].y1==s[i].y2){
            int x1=s[i].x1,x2=s[i].x2;
            for(int j=min(x1,x2);j<=max(x1,x2);j++){
                mp[j][s[i].y1]++;
            }
        }
    }
}
int tx[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
void bfs(int x,int y,int flag){

    queue<pair<int,int>>Q;
    Q.push(make_pair(x,y));
    while(!Q.empty()){
        pair<int,int>u;
        u=Q.front(); Q.pop();
        a[u.first][u.second]=flag;
        for(int i=0;i<4;i++){
            int dx=tx[i][0]+u.first;
            int dy=tx[i][1]+u.second;
            if(dx<1||dx>n||dy<1||dy>m) continue;
            if(!vis[dx][dy]&&!mp[dx][dy]){
                vis[dx][dy]=1;
                Q.push(make_pair(dx,dy));
            }
        }
    }
}

int anss=0,anx[maxn*10];
int fin(int x){
    return b[x]==x?x:b[x]=fin(b[x]);
}
void solve(){

    anss=top;
    for(int i=p;i>=1;i--){
        anx[i]=anss;
        if(s[i].x1==s[i].x2){
            int y1=s[i].y1,y2=s[i].y2;
            for(int j=min(y1,y2);j<=max(y1,y2);j++){
                mp[s[i].x1][j]--;
                if(!mp[s[i].x1][j]) a[s[i].x1][j]=++top,anss++;
            }
            for(int j=min(y1,y2);j<=max(y1,y2);j++){
                if(mp[s[i].x1][j])  continue;
                int fx=fin(a[s[i].x1][j]);
                for(int k=0;k<4;k++){
                    int dx=tx[k][0]+s[i].x1;
                    int dy=tx[k][1]+j;
                    if(dx<1||dx>n||dy<1||dy>m) continue;
                    if(!mp[dx][dy]){
                        int fy=fin(a[dx][dy]);
                        if(fx!=fy){
                            b[fy]=fx;
                            anss--;
                        }
                    }
                }
            }
        }
        else if(s[i].y1==s[i].y2){
            int x1=s[i].x1,x2=s[i].x2;
            for(int j=min(x1,x2);j<=max(x1,x2);j++){
                mp[j][s[i].y1]--;
                if(!mp[j][s[i].y1]) a[j][s[i].y1]=++top,anss++;
            }
            for(int j=min(x1,x2);j<=max(x1,x2);j++){
                if(mp[j][s[i].y1])  continue;
                int fx=fin(a[j][s[i].y1]);
                for(int k=0;k<4;k++){
                    int dx=tx[k][0]+j;
                    int dy=tx[k][1]+s[i].y1;
                    if(dx<1||dx>n||dy<1||dy>m) continue;
                    if(!mp[dx][dy]){
                        int fy=fin(a[dx][dy]);
                        if(fx!=fy){
                            b[fy]=fx;
                            anss--;
                        }
                    }
                }
            }
        }
    }
}
int main()
{
    scanf("%d %d %d",&n,&m,&p);
    for(int i=1;i<=p;i++){
        scanf("%d %d %d %d",&s[i].x1,&s[i].y1,&s[i].x2,&s[i].y2);
    }
    init();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){

            if(!mp[i][j]&&!vis[i][j]){
                ++top;
                bfs(i,j,top);
            }
        }
    }

    solve();

    for(int i=1;i<=p;i++) printf("%d\n",anx[i]);
    return 0;
}