Promising String

 

https://codeforces.com/contest/1660/problem/F2

题意

给出一个仅仅包含’+’ ‘-‘的字符串,我们可以将两个连续的’-‘,合并为’+’。
求其所有子串经历变换后 ‘+’ 的数量等于 ‘-‘ 的数量的个数。

思路

假若,我们有一段连续的序列了,其中有 x 个 ‘+’ , y 个 ‘-‘。

那么我们如果想要成立的话,那么我们需要以下几个条件成立。

  • y >= x
  • x + k = y - k * 2y - x = 3 * k

也就是说,我们只需要 (y - x) % 3 = 0 情况下的答案。

首先,如果,我们用 -+ 把所有的 + 排完。那么我们就得到 k >= (y - x) / 2。而我们需要的数量为 (y - x) / 3 < (y - x) / 2 。因此,我们的 k 约束百分之百成立。

那么最后,我们记录前缀和,我们只考虑 (m[R] - m[L]) - (p[R] - p[L]) 模三得 0 的个数。

那么我们开三个树状数组完成统计即可。

code

algorithm