Binary String Copying (Codeforces 1849C)
Tags: Others, hashing

You are given a string $$$s$$$ consisting of $$$n$$$ characters 0 and/or 1.You make $$$m$$$ copies of this string, let the $$$i$$$-th copy be the string $$$t_i$$$. Then you perform exactly one operation on each of the copies: for the $$$i$$$-th copy, you sort its substring $$$[l_i; r_i]$$$ (the substring from the $$$l_i$$$-th character to the $$$r_i$$$-th character, both endpoints inclusive). Note that each operation affects only one copy, and each copy is affected by only one operation.Your task is to calculate the number of different strings among $$$t_1, t_2, \ldots, t_m$$$. Note that the initial string $$$s$$$ should be counted only if at least one of the copies stays the same after the operation.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the length of $$$s$$$ and the number of copies, respectively.The second line contains $$$n$$$ characters 0 and/or 1 — the string $$$s$$$.Then $$$m$$$ lines follow. The $$$i$$$-th of them contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — the description of the operation applied to the $$$i$$$-th copy.The sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$. The sum of $$$m$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output: Print one integer — the number of different strings among $$$t_1, t_2, \ldots, t_m$$$.

Note: Consider the first example. Copies below are given in order of the input operations. Underlined substrings are substrings that are sorted:  101100 $$$\rightarrow$$$ 011100;  101100 $$$\rightarrow$$$ 011100;  101100 $$$\rightarrow$$$ 101100;  101100 $$$\rightarrow$$$ 101100;  101100 $$$\rightarrow$$$ 000111. There are three different strings among $$$t_1, t_2, t_3, t_4, t_5$$$: 000111, 011100 and 101100.Consider the second example:  100111 $$$\rightarrow$$$ 100111;  100111 $$$\rightarrow$$$ 001111;  100111 $$$\rightarrow$$$ 001111;  100111 $$$\rightarrow$$$ 010111. There are three different strings among $$$t_1, t_2, t_3, t_4$$$: 001111, 010111 and 100111.

Sample Inputs:
3
6 5
101100
1 2
1 3
2 4
5 5
1 6
6 4
100111
2 2
1 4
1 3
1 2
1 1
0
1 1

Sample Outputs:
3
3
1

Solution (Python):
import sys

def solve():
    (n, m) = map(int, input().split())
    s = sys.stdin.readline().strip()
    l = [-1] * (n + 2)
    r = [n + 2] * (n + 2)
    for i in range(1, n + 1):
        l[i] = l[i - 1]
        if s[i - 1] == '0':
            l[i] = i
    for i in range(n, 0, -1):
        r[i] = r[i + 1]
        if s[i - 1] == '1':
            r[i] = i
    S = set()
    for _ in range(m):
        (a, b) = map(int, sys.stdin.readline().split())
        (x, y) = (r[a], l[b])
        if x < y:
            S.add((x, y))
        else:
            S.add((0, 0))
    print(len(S))
T = int(input())
for _ in range(T):
    solve()

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, m) = readInts()
    s = readStr()
    (r1, l0) = ([-1] * n, [-1] * n)
    (z, o) = ([], [])
    for i in range(n):
        if s[i] == '1':
            while z:
                r1[z.pop()] = i
        else:
            z.append(i)
        j = n - 1 - i
        if s[j] == '0':
            while o:
                l0[o.pop()] = j
        else:
            o.append(j)
    S = set()
    og = 0
    for i in range(m):
        (l, r) = readInts()
        l -= 1
        r -= 1
        if l == r:
            og = 1
            continue
        u = v = -1
        if s[l] == '0':
            if r1[l] == -1 or r1[l] >= r:
                og = 1
                continue
            else:
                u = r1[l]
                if s[r] == '0':
                    v = r
                elif l0[r] > u:
                    v = l0[r]
                else:
                    og = 1
                    continue
        else:
            u = l
            if s[r] == '1':
                if l0[r] == -1 or l0[r] <= l:
                    og = 1
                    continue
                else:
                    v = l0[r]
            else:
                v = r
        S.add((u, v))
    return len(S) + og
for _ in range(int(input())):
    print(solve())

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, m) = readInts()
    s = readStr()
    (r1, l0) = ([n] * n, [-1] * n)
    (z, o) = ([], [])
    for i in range(n):
        if s[i] == '1':
            while z:
                r1[z.pop()] = i
            r1[i] = i
        else:
            z.append(i)
        j = n - 1 - i
        if s[j] == '0':
            while o:
                l0[o.pop()] = j
            l0[j] = j
        else:
            o.append(j)
    S = set()
    og = 0
    for i in range(m):
        (l, r) = readInts()
        if r1[l - 1] < l0[r - 1]:
            S.add((r1[l - 1], l0[r - 1]))
        else:
            og = 1
    return len(S) + og
for _ in range(int(input())):
    print(solve())