Promising String (hard version)

题意翻译

如果一个非空字符串包含了相同个数的加号与减号，我们把它称之为一个平衡字符串。 比如`+--+`,`++-+--`都是平衡的，而字符串`+--`,`--`,` `都不是平衡的。 如果一个字符串可以通过几个（可以是$0$个）操作而变得平衡，我们称它是有希望的。具体操作为： 把两个相邻的减号替换为一个加号 显然所有的平衡字符串都是有希望的，不过不是所有有希望的字符串都是平衡的。比如字符串`-+---`是一个有希望的字符串。因为 你可以把两个相邻的减号替换为一个加号从而达到一个平衡字符串`-++-`或`-+-+` 对于一个给定的字符串$s$,你要求出有它多少个非空子串是有希望的。如果一个子串在$s$中出现了多次，我们也要计算多次 **输入格式** 第一行输入一个正整数$t$($1 \leq t \leq 10^4$)，代表有多少个测试数据 对于每一个测试数据，输入两行。 第一行一个正整数$n$($1 \leq n \leq 2 \times 10^5$),表示字符串$s$的长度 第二行输入一个字符串$s$,仅由`+`,`-`构成 保证对于所有测试数据，$n$的和不会超过$2 \times 10^5$ **输出格式** 对于每一个输出数据，输出它多少个非空子串是有希望的。

题目描述

This is the hard version of Problem F. The only difference between the easy version and the hard version is the constraints. We will call a non-empty string balanced if it contains the same number of plus and minus signs. For example: strings "+--+" and "++-+--" are balanced, and strings "+--", "--" and "" are not balanced. We will call a string promising if the string can be made balanced by several (possibly zero) uses of the following operation: - replace two adjacent minus signs with one plus sign. In particular, every balanced string is promising. However, the converse is not true: not every promising string is balanced. For example, the string "-+---" is promising, because you can replace two adjacent minuses with plus and get a balanced string "-++-", or get another balanced string "-+-+". How many non-empty substrings of the given string $ s $ are promising? Each non-empty promising substring must be counted in the answer as many times as it occurs in string $ s $ . Recall that a substring is a sequence of consecutive characters of the string. For example, for string "+-+" its substring are: "+-", "-+", "+", "+-+" (the string is a substring of itself) and some others. But the following strings are not its substring: "--", "++", "-++".

输入输出格式

输入格式

The first line of the input contains an integer $ t $ ( $ 1 \le t \le 10^4 $ ) —the number of test cases in the test. Then the descriptions of test cases follow. Each test case of input data consists of two lines. The first line consists of the number $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ): the length of $ s $ . The second line of the test case contains the string $ s $ of length $ n $ , consisting only of characters "+" and "-". It is guaranteed that the sum of values $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print a single number: the number of the promising non-empty substrings of string $ s $ . Each non-empty promising substring must be counted in the answer as many times as it occurs in string $ s $ .

输入输出样例

输入样例 #1

5
3
+-+
5
-+---
4
----
7
--+---+
6
+++---

输出样例 #1

2
4
2
7
4

说明

The following are the promising substrings for the first three test cases in the example: 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] $ ="---".

题意翻译

如果一个非空字符串包含了相同个数的加号与减号，我们把它称之为一个平衡字符串。 比如`+--+`,`++-+--`都是平衡的，而字符串`+--`,`--`,` `都不是平衡的。 如果一个字符串可以通过几个（可以是$0$个）操作而变得平衡，我们称它是有希望的。具体操作为： 把两个相邻的减号替换为一个加号 显然所有的平衡字符串都是有希望的，不过不是所有有希望的字符串都是平衡的。比如字符串`-+---`是一个有希望的字符串。因为 你可以把两个相邻的减号替换为一个加号从而达到一个平衡字符串`-++-`或`-+-+` 对于一个给定的字符串$s$,你要求出有它多少个非空子串是有希望的。如果一个子串在$s$中出现了多次，我们也要计算多次 **输入格式** 第一行输入一个正整数$t$($1 \leq t \leq 10^4$)，代表有多少个测试数据 对于每一个测试数据，输入两行。 第一行一个正整数$n$($1 \leq n \leq 2 \times 10^5$),表示字符串$s$的长度 第二行输入一个字符串$s$,仅由`+`,`-`构成 保证对于所有测试数据，$n$的和不会超过$2 \times 10^5$ **输出格式** 对于每一个输出数据，输出它多少个非空子串是有希望的。