Sum over all Substrings (Hard Version) (Codeforces 1930D2)
Tags: Greedy, divide and conquer

This is the hard version of the problem. The only difference between the two versions is the constraint on $$$t$$$ and $$$n$$$. You can make hacks only if both versions of the problem are solved.For a binary$$$^\dagger$$$ pattern $$$p$$$ and a binary string $$$q$$$, both of length $$$m$$$, $$$q$$$ is called $$$p$$$-good if for every $$$i$$$ ($$$1 \leq i \leq m$$$), there exist indices $$$l$$$ and $$$r$$$ such that:   $$$1 \leq l \leq i \leq r \leq m$$$, and  $$$p_i$$$ is a mode$$$^\ddagger$$$ of the string $$$q_l q_{l+1} \ldots q_{r}$$$. For a pattern $$$p$$$, let $$$f(p)$$$ be the minimum possible number of $$$\mathtt{1}$$$s in a $$$p$$$-good binary string (of the same length as the pattern).You are given a binary string $$$s$$$ of size $$$n$$$. Find $$$$$$\sum_{i=1}^{n} \sum_{j=i}^{n} f(s_i s_{i+1} \ldots s_j).$$$$$$ In other words, you need to sum the values of $$$f$$$ over all $$$\frac{n(n+1)}{2}$$$ substrings of $$$s$$$.$$$^\dagger$$$ A binary pattern is a string that only consists of characters $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$.$$$^\ddagger$$$ Character $$$c$$$ is a mode of string $$$t$$$ of length $$$m$$$ if the number of occurrences of $$$c$$$ in $$$t$$$ is at least $$$\lceil \frac{m}{2} \rceil$$$. For example, $$$\mathtt{0}$$$ is a mode of $$$\mathtt{010}$$$, $$$\mathtt{1}$$$ is not a mode of $$$\mathtt{010}$$$, and both $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$ are modes of $$$\mathtt{011010}$$$.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the length of the binary string $$$s$$$.The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$ consisting of only characters $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each test case, output the sum of values of $$$f$$$ over all substrings of $$$s$$$.

Note: In the first test case, the only $$$\mathtt{1}$$$-good string is $$$\mathtt{1}$$$. Thus, $$$f(\mathtt{1})=1$$$.In the second test case, $$$f(\mathtt{10})=1$$$ because $$$\mathtt{01}$$$ is $$$\mathtt{10}$$$-good, and $$$\mathtt{00}$$$ is not $$$\mathtt{10}$$$-good. Thus, the answer is $$$f(\mathtt{1})+f(\mathtt{10})+f(\mathtt{0}) = 1 + 1 + 0 = 2$$$.In the third test case, $$$f$$$ equals to $$$0$$$ for all $$$1 \leq i \leq j \leq 5$$$. Thus, the answer is $$$0$$$.

Sample Inputs:
4
1
1
2
10
5
00000
20
11110110000000111111

Sample Outputs:
1
2
0
346

Solution (Python):
def thing(s):
    dp = [0] * (len(s) + 10)
    for i in range(len(s) - 1, -1, -1):
        if s[i] == '1':
            dp[i] = dp[i + 3] + len(s) - i
        else:
            dp[i] = dp[i + 1]
    return sum(dp)
testcases = range(int(input()))
for case in testcases:
    input()
    print(thing(input()))

Solution (Python):
def res(n, m):
    s = '?' + m
    l = [0] * (n + 1)
    out = 0
    for i in range(n, 0, -1):
        if s[i] == '1':
            if i + 3 <= n:
                l[i] = n + 1 - i + l[i + 3]
            else:
                l[i] = n + 1 - i
        elif i + 1 <= n:
            l[i] = l[i + 1]
        else:
            l[i] = 0
        out += l[i]
    print(out)
t = int(input())
for _ in range(t):
    n = int(input())
    t1 = input()
    res(n, t1)

Solution (Python):
def res(n, m):
    s = '?' + m
    l = [0] * (n + 1)
    out = 0
    for i in range(n, 0, -1):
        if s[i] == '1':
            if i + 3 <= n:
                l[i] = n + 1 - i + l[i + 3]
            else:
                l[i] = n + 1 - i
        elif i + 1 <= n:
            l[i] = l[i + 1]
        else:
            l[i] = 0
        out += l[i]
    print(out)
t = int(input())
for _ in range(t):
    n = int(input())
    t1 = input()
    res(n, t1)