Narrow Components (Codeforces 1661E)
Tags: Math, dsu

You are given a matrix $$$a$$$, consisting of $$$3$$$ rows and $$$n$$$ columns. Each cell of the matrix is either free or taken.A free cell $$$y$$$ is reachable from a free cell $$$x$$$ if at least one of these conditions hold:   $$$x$$$ and $$$y$$$ share a side;  there exists a free cell $$$z$$$ such that $$$z$$$ is reachable from $$$x$$$ and $$$y$$$ is reachable from $$$z$$$. A connected component is a set of free cells of the matrix such that all cells in it are reachable from one another, but adding any other free cell to the set violates this rule.You are asked $$$q$$$ queries about the matrix. Each query is the following:   $$$l$$$ $$$r$$$ — count the number of connected components of the matrix, consisting of columns from $$$l$$$ to $$$r$$$ of the matrix $$$a$$$, inclusive. Print the answers to all queries.

Input: The first line contains an integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the number of columns of matrix $$$a$$$.The $$$i$$$-th of the next three lines contains a description of the $$$i$$$-th row of the matrix $$$a$$$ — a string, consisting of $$$n$$$ characters. Each character is either $$$1$$$ (denoting a free cell) or $$$0$$$ (denoting a taken cell).The next line contains an integer $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — the number of queries.The $$$j$$$-th of the next $$$q$$$ lines contains two integers $$$l_j$$$ and $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — the description of the $$$j$$$-th query.

Output: Print $$$q$$$ integers — the $$$j$$$-th value should be equal to the number of the connected components of the matrix, consisting of columns from $$$l_j$$$ to $$$r_j$$$ of the matrix $$$a$$$, inclusive.


Sample Inputs:
12
100101011101
110110010110
010001011101
8
1 12
1 1
1 2
9 9
8 11
9 12
11 12
4 6

Sample Outputs:
7
1
1
2
1
3
3
3

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]
from collections import defaultdict

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            (x, y) = (y, x)
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for (i, x) in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

class segtree:

    def __init__(self, init, func, ide):
        self.n = len(init)
        self.func = func
        self.ide = ide
        self.size = 1 << (self.n - 1).bit_length()
        self.tree = [self.ide for i in range(2 * self.size)]
        for i in range(self.n):
            self.tree[self.size + i] = init[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.func(self.tree[2 * i], self.tree[2 * i | 1])

    def update(self, k, x):
        k += self.size
        self.tree[k] = x
        k >>= 1
        while k:
            self.tree[k] = self.func(self.tree[2 * k], self.tree[k * 2 | 1])
            k >>= 1

    def get(self, i):
        return self.tree[i + self.size]

    def query(self, l, r):
        l += self.size
        r += self.size
        l_res = self.ide
        r_res = self.ide
        while l < r:
            if l & 1:
                l_res = self.func(l_res, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_res = self.func(self.tree[r], r_res)
            l >>= 1
            r >>= 1
        return self.func(l_res, r_res)

    def debug(self, s=10):
        print([self.get(i) for i in range(min(self.n, s))])
n = int(input())
s = [input() for i in range(3)]
cum1 = [0]
tmp = 0
for i in range(n):
    for j in range(3):
        if s[j][i] == '1':
            tmp += 1
        if j != 2 and s[j][i] == s[j + 1][i] == '1':
            tmp -= 1
    cum1.append(tmp)
cum2 = [0]
tmp = 0

def conv(x, y):
    return n * x + y
todo = [-1] * n
last = -1
uf = UnionFind(n * 3)
for i in range(n):
    for j in range(2):
        if s[j][i] == s[j + 1][i] == '1':
            uf.union(conv(j, i), conv(j + 1, i))
    if i == 0:
        if s[0][i] + s[1][i] + s[2][i] == '111':
            last = i
        continue
    flag = False
    for j in range(3):
        if s[j][i - 1] == s[j][i] == '1':
            if not uf.same(conv(j, i - 1), conv(j, i)):
                tmp += 1
                uf.union(conv(j, i - 1), conv(j, i))
            else:
                flag = True
    if s[0][i] + s[1][i] + s[2][i] == '111' and s[0][i - 1] + s[1][i - 1] + s[2][i - 1] == '101':
        if flag:
            todo[last] = i
    if s[0][i] + s[1][i] + s[2][i] == '111':
        last = i
    cum2.append(tmp)
query = [[] for i in range(n)]
q = int(input())
for i in range(q):
    (l, r) = map(lambda x: int(x) - 1, input().split())
    query[l].append((r, i))
seg = segtree([0] * n, lambda x, y: x + y, 0)
ans = [0] * q
for l in range(n):
    for (r, id) in query[l]:
        ans[id] = cum1[r + 1] - cum1[l] - (cum2[r] - cum2[l]) - seg.query(l, r)
    if todo[l] != -1:
        seg.update(todo[l] - 1, 1)
for i in ans:
    print(i)

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_root(s, root):
    if s ^ root[s]:
        root[s] = get_root(root[s], root)
        return root[s]
    return s

def unite(s, t, root):
    (rs, rt) = (get_root(s, root), get_root(t, root))
    root[rt] = rs
    return

def same(s, t, root):
    return True if get_root(s, root) == get_root(t, root) else False

def merge(u, v, s0):
    x = v
    root = []
    for _ in range(6):
        root.append((x & 7) + 6 if x & 7 else 0)
        x >>= 3
    x = u
    for _ in range(6):
        root.append(x & 7)
        x >>= 3
    root.append(0)
    root.reverse()
    s = s0
    for i in range(4, 7):
        if root[i] and root[i + 3] and (not same(i, i + 3, root)):
            unite(i, i + 3, root)
            s -= 1
    x = []
    for i in range(1, 4):
        if root[i]:
            x.append(get_root(i, root))
        else:
            x.append(0)
    for i in range(10, 13):
        if root[i]:
            x.append(get_root(i, root))
        else:
            x.append(0)
    d = dict()
    w = 0
    for i in range(6):
        w <<= 3
        if not x[i]:
            continue
        elif not x[i] in d:
            d[x[i]] = i + 1
        w ^= d[x[i]]
    return (w, s)
n = int(input())
y = []
for i in range(2):
    for j in range(2):
        for k in range(2):
            u = i & 1 ^ (j & 1) << 1 ^ (k & 1) << 2
            v = 0
            x = [i]
            if not j & 1:
                x.append(0)
            elif i & j & 1:
                x.append(x[-1])
            else:
                x.append(2)
            if not k & 1:
                x.append(0)
            elif j & k & 1:
                x.append(x[-1])
            else:
                x.append(3)
            for _ in range(2):
                for l in x:
                    v <<= 3
                    v ^= l
            y.append(v)
z = [0, 1, 1, 1, 1, 2, 1, 1]
a1 = list(input().rstrip())
a2 = list(input().rstrip())
a3 = list(input().rstrip())
l1 = pow(2, n.bit_length())
l2 = 2 * l1
tree = [0] * l2
size = [0] * l2
for i in range(n):
    u = a1[i] & 1 ^ (a2[i] & 1) << 1 ^ (a3[i] & 1) << 2
    tree[i + l1] = y[u]
    size[i + l1] = z[u]
for i in range(l1 - 1, 0, -1):
    (j, k) = (i << 1, i << 1 ^ 1)
    (tree[i], size[i]) = merge(tree[j], tree[k], size[j] + size[k])
q = int(input())
ans = []
for _ in range(q):
    (l, r) = map(int, input().split())
    (s, t) = (l + l1 - 1, r + l1 - 1)
    (u, v) = ([], [])
    while s <= t:
        if s & 1:
            u.append(s)
            s += 1
        s >>= 1
        if s > t:
            break
        if not t & 1:
            v.append(t)
            t -= 1
        t >>= 1
    u += v[::-1]
    root = []
    ans0 = 0
    while u:
        i = u.pop()
        x = tree[i]
        ans0 += size[i]
        l = 6 * len(u)
        for _ in range(6):
            root.append((x & 7) + l if x & 7 else 0)
            x >>= 3
    root.append(0)
    root.reverse()
    for i in range(4, len(root) - 3, 6):
        for j in range(3):
            if root[i + j] and root[i + j + 3] and (not same(i + j, i + j + 3, root)):
                unite(i + j, i + j + 3, root)
                ans0 -= 1
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys

def Column2Num(m, idx):
    return int(m[0][idx] != 0) | int(m[1][idx]) << 1 | int(m[2][idx]) << 2

def QColumn(m, bits, idx):
    if bits[idx] == 5:
        if m[0][idx] == m[2][idx]:
            return True
    return False

def GetIntegratedCount(m):
    (ret, curr) = ([0], set())
    for c in range(len(m[0])):
        if m[0][c] != 0:
            curr.add(m[0][c])
        if m[1][c] != 0:
            curr.add(m[1][c])
        if m[2][c] != 0:
            curr.add(m[2][c])
        ret.append(len(curr))
    ret.append(len(curr))
    return ret

def Print(tm):
    print('\n', tm[0], '\n', tm[1], '\n', tm[2])

def PrintIndexed(tm):
    for i in range(len(tm[0])):
        print(i + 1, ':', tm[0][i], tm[1][i], tm[2][i])

def next(b, next):
    b &= next
    if b == 0:
        return b
    if b & 1 or b & 4:
        if next & 2:
            b |= 2
    if b & 2:
        if next & 1:
            b |= 1
        if next & 4:
            b |= 4
    return b

def setCompNumber(b, m, i, compNumber):
    if b & 1:
        m[0][i] = compNumber
    if b & 2:
        m[1][i] = compNumber
    if b & 4:
        m[2][i] = compNumber

def goLeft(start, compNumber, size, m, bits, fullColumn):
    b = bits[start]
    fc = start
    for i in range(start - 1, -1, -1):
        b = next(b, bits[i])
        if b == 7:
            fc = i
            break
        if b == 0:
            break
        setCompNumber(b, m, i, compNumber)
        if b == 5:
            fullColumn[i] = fc

def goRight(start, compNumber, size, m, bits, fullColumn):
    b = bits[start]
    for i in range(start, size):
        b = next(b, bits[i])
        if b == 7:
            fc = i
        if b == 0:
            break
        setCompNumber(b, m, i, compNumber)
        if b == 5:
            fullColumn[i] = fc

def goRight12(b, start, compNumber, size, m, bits):
    for i in range(start, size):
        b = next(b, bits[i])
        if b == 0:
            break
        setCompNumber(b, m, i, compNumber)

def get3Components(compNumber, size, m, bits, leftFullColumn, rightFullColumn):
    for i in range(size):
        if bits[i] == 7:
            if m[0][i] == 1:
                compNumber += 1
                goRight(i, compNumber, size, m, bits, leftFullColumn)
            goLeft(i, compNumber, size, m, bits, rightFullColumn)
    return compNumber

def get12Components(compNumber, size, m, bits):
    for i in range(size):
        if m[0][i] == 1:
            compNumber += 1
            goRight12(1, i, compNumber, size, m, bits)
        if m[1][i] == 1:
            compNumber += 1
            goRight12(2, i, compNumber, size, m, bits)
        if m[2][i] == 1:
            compNumber += 1
            goRight12(4, i, compNumber, size, m, bits)

def SolveBB(m, bits, integratedCount, s, e, leftFullColumn, rightFullColumn):
    sol1 = 0
    if s - 1 == 0:
        sol1 = integratedCount[e]
    else:
        startCnt = 1
        if bits[s - 1] == 0:
            startCnt = 0
        elif bits[s - 1] == 5:
            if m[0][s - 1] != m[2][s - 1]:
                startCnt = 2
        sol1 = startCnt + integratedCount[e] - integratedCount[s]
    sQ = QColumn(m, bits, s - 1)
    eQ = QColumn(m, bits, e - 1)
    if sQ and eQ:
        if m[0][s - 1] == m[2][s - 1]:
            if rightFullColumn[s - 1] == rightFullColumn[e - 1]:
                sol1 += 1
                return sol1
            elif leftFullColumn[s - 1] == leftFullColumn[e - 1]:
                sol1 += 1
                return sol1
    if sQ:
        if rightFullColumn[s - 1] != -1:
            if rightFullColumn[s - 1] > e - 1:
                sol1 += 1
        else:
            sol1 += 1
    if eQ:
        if leftFullColumn[e - 1] != -1:
            if leftFullColumn[e - 1] < s - 1:
                sol1 += 1
        else:
            sol1 += 1
    return sol1

def mainBB():
    debug = 0
    input = sys.stdin
    if len(sys.argv) >= 2:
        input = open(sys.argv[1], 'r')
    size = int(input.readline())
    m = []
    for i in range(3):
        m.append([int(t) for t in list(input.readline().strip())])
    bits = [Column2Num(m, i) for i in range(size)]
    leftFullColumn = [-1 for i in range(size)]
    rightFullColumn = list(leftFullColumn)
    compNumber = get3Components(1, size, m, bits, leftFullColumn, rightFullColumn)
    get12Components(compNumber, size, m, bits)
    integratedCount = GetIntegratedCount(m)
    if debug:
        PrintIndexed(m)
    if debug:
        Print(m)
    if debug:
        print(integratedCount)
    if debug:
        print(leftFullColumn)
    if debug:
        print(rightFullColumn)
    n = int(input.readline())
    for i in range(n):
        ln = input.readline().strip().split()
        s = int(ln[0])
        e = int(ln[1])
        if debug:
            print(s, e, m)
        print(SolveBB(m, bits, integratedCount, s, e, leftFullColumn, rightFullColumn))
if __name__ == '__main__':
    mainBB()