2018湖南多校第一场(NCPC2016)-A-Artwork

Artwork

Description

A template for an artwork is a white grid of n × m squares. The artwork will be created by painting q horizontal and vertical black strokes. A stroke starts from square (x1, y1), ends at square (x2,y2)(x1=x2 or y1=y2) and changes the color of all squares (x, y) to black where x1 ≤ x ≤ x2 and y1 ≤ y ≤ y2. The beauty of an artwork is the number of regions in the grid. Each region consists of one or more white squares that are connected to each other using a path of white squares in the grid, walking horizontally or vertically but not diagonally. The initial beauty of the artwork is 1. Your task is to calculate the beauty after each new stroke. Figure A.1 illustrates how the beauty of the artwork varies in Sample Input 1.

Input

The first line of input contains three integers n, m and q (1 ≤ n, m ≤ 1000, 1 ≤ q ≤ 104). Then follow q lines that describe the strokes. Each line consists of four integersx1,y1,x2 and y2(1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m). Either x1 = x2 or y1=y2(or both).

Output

For each of the q strokes, output a line containing the beauty of the artwork after the stroke.

Sample Input

4 6 5
2 2 2 6
1 3 4 3
2 5 3 5
4 6 4 6
1 6 4 6

Sample Output

1
3
3
4
3

题目大意：给出一个$n\times m$的格子，每次涂黑一行或一列，问每次涂完后白色的连通块有多少。
解题思路：求连通块，想到并查集，DFS，类似那种炸铁路求连通块的题，倒着做。统计最后出最后白色连通块的数目，然后对每一个询问，取消一个黑色块（即变白色），ans++，这个块与相邻块合并，ans - -。对于格子可以hash一下，方便用并查集。
复杂度： $O(n*m)$

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>
#define mk make_pair
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int MAXN=1e3+5;
const int MAXQ=1e4+5;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int fa[MAXN*MAXN];
bool black[MAXN][MAXN];
int n,m,q,ans;
vector<PII> v[MAXQ];
vector<int> ret;

int Find(int x){
    return fa[x]==x?x:fa[x]=Find(fa[x]);
}

bool Union(int x1,int y1,int x2,int y2){
    int u=x1*m+y1,v=x2*m+y2;
    int fu=Find(u),fv=Find(v);
    if(fu!=fv){
        fa[fu]=fv;
        return true;
    }
    return false;
}

void Init(){
    memset(black,false,sizeof(black));
    for(int i=1;i<=q;i++) v[i].clear();
    ret.clear();
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            fa[i*m+j]=i*m+j;
        }
    }
}

void Debug1(){
    for(int i=1;i<=q;i++){
        for(auto j : v[i]){
            cout<<j.first<<" "<<j.second<<" ";
        }
        cout<<endl;
    }
}

bool OK(int x,int y){
    if(x<0||x>=n||y<0||y>=m) return false;
    return true;
}

int main(){
    while(scanf("%d%d%d",&n,&m,&q)!=EOF){
        Init();
        int x1,y1,x2,y2;
        ans=n*m;
        for(int i=1;i<=q;i++){
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            x1--;y1--;x2--;y2--;
            if(x1==x2){
                for(int j=y1;j<=y2;j++){
                    if(black[x1][j]) continue;
                    black[x1][j]=true;
                    v[i].push_back(mk(x1,j));
                    ans--;
                }
            }else{
                for(int j=x1;j<=x2;j++){
                    if(black[j][y1]) continue;
                    black[j][y1]=true;
                    v[i].push_back(mk(j,y1));
                    ans--;
                }
            }
        }
        //Debug1();
        //cout<<ans<<endl;
        int nx,ny;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!black[i][j]){
                    for(int k=0;k<4;k++){
                        nx=i+dx[k],ny=j+dy[k];
                        if(OK(nx,ny)&&(!black[nx][ny])&&Union(i,j,nx,ny)) ans--;
                    }
                }
            }
        }
        //cout<<ans<<endl;
        ret.push_back(ans);
        int x,y;
        for(int i=q;i>1;i--){
            int sz=v[i].size();
            for(int j=0;j<sz;j++){
                x=v[i][j].first;y=v[i][j].second;
//                cout<<x<<" "<<y<<endl;
                ans++;
                for(int k=0;k<4;k++){
                    nx=x+dx[k];ny=y+dy[k];
                    if(OK(nx,ny)&&(!black[nx][ny])&&Union(x,y,nx,ny)) ans--;
                }
                black[x][y]=false;
            }
            ret.push_back(ans);
        }
        for(int i=q-1;i>=0;i--){
            printf("%d\n",ret[i]);
        }

    }
    return 0;
}
/*
4 6 5
2 2 2 6
1 3 4 3
2 5 3 5
4 6 4 6
1 6 4 6
*/