题解

题面描述

给定一个长度为 $n$ 的二进制字符串 $s$（仅包含字符 '0' 和 '1'），我们可以对任意子串执行以下操作：每次添加或删除一个字符 '0' 或者字符 '1'。现在要求我们求出所有非空子串的"权值"之和。

一个子串 $t$ 的权值定义为：通过任意次数交换相邻字符的前提下，确保任意相邻的字符都不相等的最少操作次数。换句话说，最小的操作次数就是将该子串变为一个 "交替字符串"（例如 '010101' 或 '101010'）所需的操作。

思路

题目内容

对于一个字符串，小美每次操作可以:添加或者删除一个$0$字符或者$1$。

她定义一个字符串$t$的权值为:

满足任意次交换两个相邻字符的前提下使得任意相邻的两个字符都不相等的最少操作次数。

例如:对于$t=011$,其权值为$1$。

可以选择在$11$之间添加$0$变成$0101$。

也可以选择删除$1$变成$01$。

给你一个长度为$n$的字符串$s$，仅包含"$0、1$"，请你帮助小美求出非空子串的权值之和。

子串:是指一个字符串中的连续部分。

输入描述

第一行一个整数$t(1≤1≤10)$,表示数据组数。

对于每一组数据格式为:

第一行一个整数$n(1≤n≤2×10^5)$,表示字符串长度。

第二行第一个长度为n的字符串$s$，输入保证仅含"$0、1$".

单个测试文件数据保证$\sum n ≤2×10^5$。

输出描述

对于每一组数据：

每行输出一个整数，表示给定字符串的所有非空子串的权值之和。

样例1

输入

2
3
011
4
1111

输出

1
10

说明

对于第二个样例$s$="$1111$": 长度为$1$的子串$[1,1,1,1]$均不需要操作。 长度为$2$的子串$[11,11,11]$均需要操作一次，使得 $11→101$。 长度为$3$的子串$[111,111]$均需要操作两次，使得 $111→10101$。 长度为4的子串$[1111]$需要操作三次，使得 $1111→1010101$。

共累计$3×1+2×2+1×3=10$。