题面
F2. Promising String (hard version) time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output 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 𝑠 are promising? Each non-empty promising substring must be counted in the answer as many times as it occurs in string 𝑠.
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: “–”, “++”, “-++”.
Input
The first line of the input contains an integer 𝑡 (1≤𝑡≤104) —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 𝑛 (1≤𝑛≤2⋅105): the length of 𝑠.
The second line of the test case contains the string 𝑠 of length 𝑛, consisting only of characters “+” and “-“.
It is guaranteed that the sum of values 𝑛 over all test cases does not exceed 2⋅105.
Output
For each test case, print a single number: the number of the promising non-empty substrings of string 𝑠. Each non-empty promising substring must be counted in the answer as many times as it occurs in string 𝑠.
Example
inputCopy
5
3
+-+
5
-+—
4
7
–+—+
6
+++—
outputCopy
2
4
2
7
4
Note
The following are the promising substrings for the first three test cases in the example:
𝑠[1…2]=”+-“, 𝑠[2…3]=”-+”;
𝑠[1…2]=”-+”, 𝑠[2…3]=”+-“, 𝑠[1…5]=”-+—“, 𝑠[3…5]=”—“;
𝑠[1…3]=”—“, 𝑠[2…4]=”—“.
题目大意
给你一个长度为n，只包含+-符号的字符串。连续两个-可以合并成一个+。问你该字符串中有多少子串满足，经过一些合并（或没有合并）后子串中+-号数量相等。
题解
上结论： 子串中-的个数比+多，且差值是3的倍数，则记一次贡献。
首先根据狄利克雷原理（抽屉原理），如果-的个数比+多于2个即一定有两个-相连。并且进行一次操作后，+-号的差异度会+3。那么就可以进行很多次操作将差异度变为0。
这题有小数据，那么对于小数据，O(n^2)的暴力为（假设一开始差异度为n）。
1 | cur=n; |
考虑优化这个
1 | inline void solve() |