Tokitsukaze and Good 01-String (hard version)

题意翻译

#### 题目描述 这是 [CF1678B1](https://www.luogu.com.cn/problem/CF1678B1) 问题的强化版，增强的地方就是需要求出在最少操作次数的基础上最少有多少段段。 给定一个长度为 $n$ 的 $0,1$ 串，如 “11001111”。将这个字符串分为“11”，“00”，“1111”，它们的长度都是偶数，我们就称这个 $0,1$ 串为好的。反之，如果分分段后每段长度不是偶数，我们就称其为不好的。 对于每次操作，可以将 $0,1$ 串中任意的“0”或“1”修改成“0”或“1”。 本题有多组数据，对于每组数据，输出将一个不好的 $0,1$ 串变成好的所需要的最少操作次数。 #### 输入格式 第一行输入一个正整数 $T$，表示数据组数。 对于每组数据，第一行为一个偶数 $n$，表示 $0,1$ 串的长度。 第二行包含一个长度为 $n$ 的 $0,1$ 串。 #### 输出格式 对于每组数，输出最少操作次数，一个数一行。 #### 说明/提示 对于 $100\%$ 的数据，$1 \le t \le 10000，2 \le n \le 2 \times 10^5$。 样例解释： 对于第一组，把第三个、第六个、第七个改成“0”，变成“1100000000”，这个字符串就变成好的了。最少有两段。 对于第二组，字符串本身就是好的，不用操作。最少有三段。

题目描述

This is the hard version of the problem. The only difference between the two versions is that the harder version asks additionally for a minimum number of subsegments. Tokitsukaze has a binary string $ s $ of length $ n $ , consisting only of zeros and ones, $ n $ is even. Now Tokitsukaze divides $ s $ into the minimum number of contiguous subsegments, and for each subsegment, all bits in each subsegment are the same. After that, $ s $ is considered good if the lengths of all subsegments are even. For example, if $ s $ is "11001111", it will be divided into "11", "00" and "1111". Their lengths are $ 2 $ , $ 2 $ , $ 4 $ respectively, which are all even numbers, so "11001111" is good. Another example, if $ s $ is "1110011000", it will be divided into "111", "00", "11" and "000", and their lengths are $ 3 $ , $ 2 $ , $ 2 $ , $ 3 $ . Obviously, "1110011000" is not good. Tokitsukaze wants to make $ s $ good by changing the values of some positions in $ s $ . Specifically, she can perform the operation any number of times: change the value of $ s_i $ to '0' or '1' ( $ 1 \leq i \leq n $ ). Can you tell her the minimum number of operations to make $ s $ good? Meanwhile, she also wants to know the minimum number of subsegments that $ s $ can be divided into among all solutions with the minimum number of operations.

输入输出格式

输入格式

The first contains a single positive integer $ t $ ( $ 1 \leq t \leq 10\,000 $ ) — the number of test cases. For each test case, the first line contains a single integer $ n $ ( $ 2 \leq n \leq 2 \cdot 10^5 $ ) — the length of $ s $ , it is guaranteed that $ n $ is even. The second line contains a binary string $ s $ of length $ n $ , consisting only of zeros and ones. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print a single line with two integers — the minimum number of operations to make $ s $ good, and the minimum number of subsegments that $ s $ can be divided into among all solutions with the minimum number of operations.

输入输出样例

输入样例 #1

5
10
1110011000
8
11001111
2
00
2
11
6
100110

输出样例 #1

3 2
0 3
0 1
0 1
3 1

说明

In the first test case, one of the ways to make $ s $ good is the following. Change $ s_3 $ , $ s_6 $ and $ s_7 $ to '0', after that $ s $ becomes "1100000000", it can be divided into "11" and "00000000", which lengths are $ 2 $ and $ 8 $ respectively, the number of subsegments of it is $ 2 $ . There are other ways to operate $ 3 $ times to make $ s $ good, such as "1111110000", "1100001100", "1111001100", the number of subsegments of them are $ 2 $ , $ 4 $ , $ 4 $ respectively. It's easy to find that the minimum number of subsegments among all solutions with the minimum number of operations is $ 2 $ . In the second, third and fourth test cases, $ s $ is good initially, so no operation is required.

**题目大意：**

这是一个关于二进制字符串的问题，需要将字符串划分为尽可能少的连续子段，使得每个子段内的数字都相同，并且子段的长度都是偶数。每次操作可以将字符串中的某个位置的数字从0变为1，或者从1变为0。题目要求求出将一个不好的二进制字符串变为好的字符串所需的最少操作次数，以及在这些操作次数最少的情况下，字符串可以划分成的最少子段数。

**输入数据格式：**

- 第一行输入一个正整数 $ T $，表示数据组数。
- 对于每组数据，第一行为一个偶数 $ n $，表示二进制字符串的长度。
- 第二行包含一个长度为 $ n $ 的二进制字符串。

**输出数据格式：**

- 对于每组数据，输出两个整数，第一个整数表示最少操作次数，第二个整数表示在最少操作次数的情况下，字符串可以划分成的最少子段数。

**样例解释：**

- 第一组数据中，将第三个、第六个、第七个位置的数字改为0，字符串变为“1100000000”，此时字符串被划分为“11”和“00000000”两个子段，长度分别为2和8，都是偶数，所以是好的字符串。最少操作次数为3，最少子段数为2。
- 第二组数据中，字符串本身就是好的，不需要操作。最少操作次数为0，最少子段数为3。**题目大意：** 这是一个关于二进制字符串的问题，需要将字符串划分为尽可能少的连续子段，使得每个子段内的数字都相同，并且子段的长度都是偶数。每次操作可以将字符串中的某个位置的数字从0变为1，或者从1变为0。题目要求求出将一个不好的二进制字符串变为好的字符串所需的最少操作次数，以及在这些操作次数最少的情况下，字符串可以划分成的最少子段数。 **输入数据格式：** - 第一行输入一个正整数 $ T $，表示数据组数。 - 对于每组数据，第一行为一个偶数 $ n $，表示二进制字符串的长度。 - 第二行包含一个长度为 $ n $ 的二进制字符串。 **输出数据格式：** - 对于每组数据，输出两个整数，第一个整数表示最少操作次数，第二个整数表示在最少操作次数的情况下，字符串可以划分成的最少子段数。 **样例解释：** - 第一组数据中，将第三个、第六个、第七个位置的数字改为0，字符串变为“1100000000”，此时字符串被划分为“11”和“00000000”两个子段，长度分别为2和8，都是偶数，所以是好的字符串。最少操作次数为3，最少子段数为2。 - 第二组数据中，字符串本身就是好的，不需要操作。最少操作次数为0，最少子段数为3。