CF1678B2 Tokitsukaze and Good 01-String (hard version)

这是该问题的困难版本。与简单版本的唯一区别在于，困难版本还要求输出最小子段数。 Tokitsukaze 有一个长度为 $n$ 的二进制字符串 $s$，仅由 $0$ 和 $1$ 组成，且 $n$ 为偶数。 现在，Tokitsukaze 将 $s$ 划分为最少数量的连续子段，每个子段内的所有位都相同。之后，如果所有子段的长度都是偶数，则称 $s$ 是好的。 例如，如果 $s$ 为 "11001111"，可以划分为 "11"、"00" 和 "1111"。它们的长度分别为 $2$、$2$、$4$，都是偶数，因此 "11001111" 是好的。再比如，如果 $s$ 为 "1110011000"，可以划分为 "111"、"00"、"11" 和 "000"，它们的长度分别为 $3$、$2$、$2$、$3$。显然，"1110011000" 不是好的。 Tokitsukaze 想通过修改 $s$ 中某些位置的值，使 $s$ 变为好的。具体来说，她可以进行任意次数的操作：将 $s_i$ 的值改为 '0' 或 '1'（$1 \leq i \leq n$）。你能告诉她，最少需要多少次操作才能使 $s$ 变为好的？同时，在所有最小操作次数的方案中，$s$ 最少可以被划分为多少个子段？

第一行包含一个正整数 $t$（$1 \leq t \leq 10\,000$），表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$），表示字符串 $s$ 的长度，保证 $n$ 为偶数。 第二行包含一个长度为 $n$ 的二进制字符串 $s$，仅由 $0$ 和 $1$ 组成。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一行两个整数，分别表示将 $s$ 变为好的最小操作次数，以及在所有最小操作次数的方案中，$s$ 最少可以被划分为多少个子段。

在第一个测试用例中，将 $s_3$、$s_6$ 和 $s_7$ 改为 '0'，此时 $s$ 变为 "1100000000"，可以划分为 "11" 和 "00000000"，长度分别为 $2$ 和 $8$，子段数为 $2$。还有其他操作 $3$ 次使 $s$ 变为好的方案，如 "1111110000"、"1100001100"、"1111001100"，它们的子段数分别为 $2$、$4$、$4$。容易发现，在所有最小操作次数的方案中，最小子段数为 $2$。 在第二、第三和第四个测试用例中，$s$ 本身就是好的，因此不需要任何操作。 由 ChatGPT 4.1 翻译