ComentOJ-C72-4032 「佛御石之钵 -不碎的意志-」(困难版)
每行开一个并查集，每个格子的祖先表示包括其在内的右边第一个为 0 的格子
一个总的并查集，表示两个格子是否属于一个集合。
时间复杂度 $_math_inline$O\left( nm\alpha(nm) + nq \right)$math_inline_$
Code
1/* ***********************************************
2Author : Akvicor
3Created Time : Mon Oct 28 13:06:07 2019
4File Name : C2.cpp
5************************************************ */
6
7#include <bits/stdc++.h>
8
9#define FAST_IO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
10#define endl '\n'
11#define ASB using namespace std; typedef long long ll; namespace AkvicorS {
12#define ASE } int main() { return AkvicorS::sol(); }
13
14ASB
15
16int n, m, q, x1, y1, x2, y2, ans, cnt;
17char s[1010];
18
19const int MAXN = 1e3+10;
20
21int fa[MAXN][MAXN];
22int F[MAXN*MAXN];
23int id[MAXN][MAXN];
24
25int fx[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
26
27inline int find(int * f, int x){return f[x] == x ? x : f[x]=find(f, f[x]);}
28
29void merge(int x, int y){
30 ++ans;
31 id[x][y] = ++cnt; // the number of '1'
32 F[cnt] = cnt; // every '1' is the father to itself
33 int u = find(fa[x], y), v = find(fa[x], y+1); // '1' 's root is the next '0'
34 if(u != v) fa[x][u] = v;
35
36 // check the left, right, up and down
37 for(int i = 0; i < 4; ++i){
38 int tx = x + fx[i][0];
39 int ty = y + fx[i][1];
40 if(tx && ty && tx <= n && ty <= m && id[tx][ty]){
41 u = find(F, id[x][y]), v = find(F, id[tx][ty]);
42 if(u != v){ // if u and v is two union before
43 --ans;
44 F[u] = v;
45 }
46
47 }
48 }
49}
50
51void init(){
52 for(int i = 0; i <= n; ++i){
53 for(int j = 0; j <= m+1; ++j){ // Must (j <= m+1) else The line 33 while throw segment falt
54 fa[i][j] = j;
55 }
56 }
57}
58
59int sol(){
60 FAST_IO;
61
62 cin >> n >> m;
63 init();
64 for(int i = 1; i <= n; ++i){
65 cin >> (s+1);
66 for(int j = 1; j <= m; ++j){
67 if(s[j] == '1'){
68 merge(i, j);
69 }
70 }
71 }
72
73 cin >> q;
74
75 while(q--){
76 cin >> x1 >> y1 >> x2 >> y2;
77 for(int x = x1; x <= x2; ++x){
78 for(int y = find(fa[x], y1); y <= y2; y = find(fa[x], y)){
79 merge(x, y); // next '0' and merge
80 }
81 }
82 cout << ans << endl;
83 }
84
85 return 0;
86}
87
88ASE
除另有声明外，本博客文章均采用 知识共享 (Creative Commons) 署名 4.0 国际许可协议 进行许可。转载请注明原作者与文章出处。