A11322 | 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$ .</p><p> $^\\dagger$ A binary <span class="tex-font-style-it">pattern</span> is a string that only consists of characters $\\mathtt{0}$ and $\\mathtt{1}$ .</p><p> $^\\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$ .