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

这是该问题的困难版本。两个版本之间的唯一区别在于对 $t$ 和 $n$ 的约束条件。仅当该问题的两个版本均被解决时，才允许进行 hack。

对于一个长度为 $m$ 的二进制$^\dagger$ 模式 $p$ 和一个长度同样为 $m$ 的二进制字符串 $q$，若对每个 $i$（$1 \leq i \leq m$），均存在下标 $l$ 和 $r$，使得：

• $1 \leq l \leq i \leq r \leq m$，且
• $p_i$ 是子串 $q_l q_{l+1} \ldots q_{r}$ 的一个众数$^\ddagger$，

则称 $q$ 是 $p$-好（$p$-good）的。

对一个模式 $p$，定义 $f(p)$ 为所有 $p$-好二进制字符串（其长度与 $p$ 相同）中 $\mathtt{1}$ 的最少可能个数。

现给定一个长度为 $n$ 的二进制字符串 $s$。请计算

$$\sum_{i=1}^{n} \sum_{j=i}^{n} f(s_i s_{i+1} \ldots s_j).$$

换言之，你需要对 $s$ 的全部 $\frac{n(n+1)}{2}$ 个子串，求其对应的 $f$ 值之和。

$^\dagger$ 二进制模式是指仅由字符 $\mathtt{0}$ 和 $\mathtt{1}$ 组成的字符串。

$^\ddagger$ 字符 $c$ 是长度为 $m$ 的字符串 $t$ 的众数，当且仅当 $c$ 在 $t$ 中的出现次数至少为 $\lceil \frac{m}{2} \rceil$。例如：$\mathtt{0}$ 是 $\mathtt{010}$ 的众数；$\mathtt{1}$ 不是 $\mathtt{010}$ 的众数；而 $\mathtt{0}$ 和 $\mathtt{1}$ 均为 $\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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^5$）——即测试用例的数目。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^6$）——即二进制字符串 $s$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$，该字符串仅由字符 $\mathtt{0}$ 和 $\mathtt{1}$ 组成。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

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

对于每个测试用例，输出函数 $f$ 在字符串 $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$.

在第一个测试用例中，唯一的 $\mathtt{1}$-好字符串是 $\mathtt{1}$。因此，$f(\mathtt{1})=1$。

在第二个测试用例中，$f(\mathtt{10})=1$，因为 $\mathtt{01}$ 是 $\mathtt{10}$-好字符串，而 $\mathtt{00}$ 不是 $\mathtt{10}$-好字符串。因此，答案为 $f(\mathtt{1})+f(\mathtt{10})+f(\mathtt{0}) = 1 + 1 + 0 = 2$。

在第三个测试用例中，对所有 $1 \leq i \leq j \leq 5$，均有 $f=0$。因此，答案为 $0$。