21. CF-Narrow Components

题目链接：Narrow Components

区间内连通块数量相当于总的块数减去有效的边数。先用前缀和预处理出块数，然后用并查集维护前缀有效边数和。由于是从整个序列左端点开始计算的，查询的时候可能会把左边的一些不连通的块归到一起。然后注意到只有最左边是一段连续的 101 时才可能出现这种情况，所以找到第一个不是 101 的列，分类讨论：

• 如果所有的列都是 101，答案就是 \(2\)
• 如果上中下都是 1，说明左边这些都能连到右边去，答案不变
• 如果上下都是 0，说明这两段都是独立的，答案 \(+2\)
• 其余情况都是有一个可以和右边连着，另一个独立，答案 \(+1\)

做法来源于官方题解，下面的代码也是照着答案写的。细节稍微有点多。

这题还有一个加强版 P3300 [SDOI2013]城市规划，非常的麻烦。

#include 
using namespace std;
using ll = long long;
#define endl '\n'
const int maxn = 5e5 + 5;
namespace dsu {
int fa[maxn << 2], sz[maxn << 2];
void init(int n) {
    iota(fa, fa + n + 1, 0);
    fill(sz, sz + n + 1, 1);
}
int find(int x) { 
	return fa[x] == x ? fa[x] : (fa[x] = find(fa[x])); 
}
bool merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y)
        return false;
    if (sz[x] < sz[y])
        swap(x, y);
    fa[y] = x, sz[x] += sz[y];
    return true;
}
}; // namespace dsu
char str[maxn];
int a[3][maxn], tot[maxn];
int ph[maxn], pv[maxn], nxt[maxn];
void solve() {
    int n, q;
    cin >> n;
    for (int i = 0; i < 3; ++i) {
        cin >> (str + 1);
        for (int j = 1; j <= n; ++j)
            a[i][j] = (str[j] == '1');
    }
    dsu::init(n * 3);
    for (int i = 1; i <= n + 1; ++i) {
    	tot[i + 1] += tot[i];
        for (int j = 0; j < 3; ++j)
            tot[i + 1] += a[j][i];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 2; ++j) {
            if (a[j][i] && a[j + 1][i] && dsu::merge(j * n + i, j * n + n + i))
                pv[i + 1]++;
        }
        for (int j = 0; j < 3; ++j) {
            if (i > 1 && a[j][i] && a[j][i - 1] &&
                dsu::merge(j * n + i, j * n - 1 + i))
                ph[i]++;
        }
    }
    for (int i = 1; i <= n + 1; ++i) {
        pv[i] += pv[i - 1], ph[i] += ph[i - 1];
    }
    for (int i = n; i >= 1; --i) {
        if (a[0][i] && !a[1][i] && a[2][i])
            nxt[i] = nxt[i + 1] + 1;
    }
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        int pos = l + nxt[l];
        if (pos > r) {
            cout << 2 << endl;
            continue;
        }
        int cnt = tot[r + 1] - tot[pos];
        int edg = pv[r + 1] - pv[pos] + ph[r] - ph[pos];
        int ans = cnt - edg;
        if (pos != l) {
            if (a[0][pos] && a[1][pos] && a[2][pos])
                ;
            else if (!a[0][pos] && !a[2][pos])
                ans += 2;
            else
                ans++;
        }
        cout << ans << endl;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}