#P18916. [2026多校联测]糖果店

[2026多校联测]糖果店

糖果店

题目描述

如果一个非空字符串包含相同个数的加号与减号,称其为平衡字符串。例如 +--+、++-+-- 是平衡的,+--、-- 和空字符串不是。

允许进行以下操作:把两个相邻的减号替换为一个加号。如果一个字符串经过若干次操作(可以是零次)能够变得平衡,就称它为有希望的字符串。

所有平衡字符串都是有希望的,但反之不一定成立。例如 -+--- 可以变成平衡字符串 -++- 或 -+-+。

给定仅含 +、- 的字符串 ss,求有多少个非空子串是有希望的。相同子串在不同位置出现时分别计数。

输入格式

第一行一个正整数 tt,表示测试数据组数。

每组数据两行:第一行一个正整数 nn,表示字符串长度;第二行是字符串 ss。

输出格式

每组数据输出一行一个整数,表示有希望的非空子串数量。

样例 1

输入

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

输出

2
4
2
7
4

数据范围

1≤t≤1041\le t\le10^4,1≤n≤2×1051\le n\le2\times10^5,所有测试数据的 nn 之和不超过 2×1052\times10^5。

子任务 ∑n≤\sum n\le 特殊性质 分值
1 88 无 5
2 500500 10
3 50005000 25
4 2×1052\times10^5 字符全部为 - 10
5 - 的个数至多为 4040 20
6 无 30

更多样例见附加文件 samples.zip,分别对应各子任务限制。