这是问题F的困难版本。简单版本和困难版本之间的唯一区别是约束。
如果一个非空字符串包含相同数量的加号和减号,我们将其称为平衡字符串。例如:字符串“+--+”和“++-+--”是平衡的,字符串“+--”、“--”和“”是不平衡的。
如果字符串可以通过多次(可能为零)使用以下操作来平衡,我们将调用一个有希望的字符串:
- 用一个加号替换两个相邻的减号。
特别是,每个平衡弦都是有前途的。然而,反之则不然:并非每个有希望的字符串都是平衡的。
例如,字符串“-+---”是有希望的,因为您可以用加号替换两个相邻的减号并得到一个平衡的字符串“-++-”,或者得到另一个平衡的字符串“-++-+”。
给定字符串 $$$s$$$ 有多少个非空子串是有希望的?每个非空有希望的子字符串在答案中的计数必须与它在字符串 $$$s$$$ 中出现的次数一样多。
回想一下,子字符串是字符串的连续字符序列。例如,对于字符串“++-+”,其子字符串为:“+-”、“-+”、“+”、“++-+”(该字符串是其自身的子字符串)等。但以下字符串不是它的子字符串:“--”、“++”、“-++”。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中的测试用例数量。
然后是测试用例的描述。
输入数据的每个测试用例由两行组成。第一行由数字 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) 组成:$$$s$$$ 的长度。
测试用例的第二行包含长度为$$$n$$$的字符串$$$s$$$,仅由字符“+”和“-”组成。
保证所有测试用例的 $$$n$$$ 值之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个数字:字符串 $$$s$$$ 中有希望的非空子串的数量。每个非空有希望的子字符串在答案中的计数必须与它在字符串 $$$s$$$ 中出现的次数一样多。
示例
输入 #1
5 3 +-+ 5 -+--- 4 ---- 7 --+---+ 6 +++---
输出 #1
2 4 2 7 4
注意
以下是示例中前三个测试用例的有希望的子字符串:
1. $$$s[1 \dots 2]$$$="+-", $$$s[2 \dots 3]$$$="-+";
2. $$$s[1 \dots 2]$$$="-+", $$$s[2 \dots 3]$$$="+-", $$$s[1 \dots 5]$$$="-+---", $$$s[3 \dots 5]$$$="---";
3. $$$s[1 \dots 3]$$$="---", $$$s[2 \dots 4]$$$="---"。