CF1930D2.Sum over all Substrings (Hard Version)

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}$$$.

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$ .

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

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$ .