← 返回题目列表

Codeforces · 1660/F2

F2. 有前途的字符串(硬版)

中文机器翻译题面 查看原题

这是问题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]$$$="---"。