「佛御石之钵 -不碎的意志-」(困难版)

题目描述

※ 简单版与困难版的唯一区别是 n,m,q 的数据范围

给一个n×m 的网格,每个格子里有一个数字,非 00 即 11,行从上往下依次编号为 1, 2⋯,n,列从左往右依次编号为 1,2,⋯,m。

给 qq 次操作,每次给定一个以(x1​,y1​) 为左上角,(x2​,y2​) 为右下角的矩形内所有格子里的数字都变成 1。问每次操作之后,所有数字为 1 的格子构成的四连通块的个数。

若不懂四连通块的定义可见最底下的提示。

输入描述

输入第一行两个整数 n,m(1≤n,m≤1000),表示网格大小。

接下来 n 行,每行一个长为 m 的 01 串,表示初始网格。

接下来一行一个整数 q (1≤q≤30000),表示操作个数。

接下来 qq 行,每行四个整数 x1​,y1​,x2​,y2​ (1≤x1​≤x2​≤n,1≤y1​≤y2​≤m) 表示把以 (x1​,y1​) 为左上角,(x2​,y2​) 为右下角的矩形中的元素都变成 1。

 输出描述

输出共 qq 行,每行一个整数,表示每次操作后含有数字 1 的格子构成的四连通块的个数。

解题思路:维护两个并查集, 对于每行开一个有关连续1的并查集,指向最右边的1。对于整体开一个并查集统计联通块。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
const int N=1005;
int n,m,ans,cnt;
char s[N][N];
int id[N][N],p[maxn],fa[N][N];
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int find(int x) {return x==p[x]?x:p[x]=find(p[x]);}
int ff(int x,int y) {return y==fa[x][y]?y:fa[x][y]=ff(x,fa[x][y]);}
void dfs(int x,int y)
{
    ans++;id[x][y]=++cnt;p[cnt]=cnt;
    int rx=ff(x,y),ry=ff(x,y+1);
    if(rx!=ry) fa[x][rx]=ry;
    for(int i=0;i<4;i++){
        int xx=x+dir[i][0],yy=y+dir[i][1];
        if(xx<1||xx>n||yy<1||yy>m||id[xx][yy]==0) continue;
        rx=find(id[x][y]),ry=find(id[xx][yy]);
        if(rx!=ry) p[rx]=ry,ans--;
     }
}
int main()
{
    int q;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) for(int j=1;j<=m+1;j++) fa[i][j]=j;
    for(int i=1;i<=n;i++){
        scanf("%s",s[i]+1);
        for(int j=1;j<=m;j++) if(s[i][j]=='1') dfs(i,j);
    }
    scanf("%d",&q);
    while(q--){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        for(int i=x1;i<=x2;i++){
            for(int j=ff(i,y1);j<=y2;j=ff(i,y1)) dfs(i,j);
        }
        printf("%d\n",ans); 
    } 
} 

 

 

 

上一篇:18-canvas绘制饼状图


下一篇:Comet OJ - Contest #13 「佛御石之钵 -不碎的意志-」(困难版) 并查集