CF1930D2 Sum over all Substrings (Hard Version)

这是该问题的困难版本。两种版本的唯一区别在于 $ t $ 和 $ n $ 的限制。只有在两种版本都解决后，你才能进行 hack。 对于一个二进制模式 $ p $ 和一个二进制字符串 $ q $，它们长度均为 $ m $，如果对于每个 $ 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} $ 的众数， 则称 $ q $ 是 $ p $-good 的。 对于一个模式 $ p $，记 $ f(p) $ 为长度与 $ p $ 相同的 $ p $-good 二进制字符串中 $ \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} $ 的众数。

每组测试包含多个测试用例。第一行包含一个整数 $ t $（$ 1 \le t \le 10^5 $）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $（$ 1 \le n \le 10^6 $）——二进制字符串 $ s $ 的长度。 每个测试用例的第二行包含一个长度为 $ n $ 的二进制字符串 $ s $，仅包含字符 $ \mathtt{0} $ 和 $ \mathtt{1} $。 保证所有测试用例中 $ n $ 的总和不超过 $ 10^6 $。

对于每个测试用例，输出 $ s $ 的所有子串的 $ f $ 值之和。

在第一个测试用例中，唯一的 $ \mathtt{1} $-good 字符串是 $ \mathtt{1} $。因此，$ f(\mathtt{1})=1 $。 在第二个测试用例中，$ f(\mathtt{10})=1 $，因为 $ \mathtt{01} $ 是 $ \mathtt{10} $-good，而 $ \mathtt{00} $ 不是 $ \mathtt{10} $-good。因此，答案为 $ f(\mathtt{1})+f(\mathtt{10})+f(\mathtt{0}) = 1 + 1 + 0 = 2 $。 在第三个测试用例中，对于所有 $ 1 \leq i \leq j \leq 5 $，$ f $ 都等于 $ 0 $。因此，答案为 $ 0 $。 由 ChatGPT 4.1 翻译