CF653F Paper task

题意：给出一个长为 的括号串，求本质不同的合法括号子串数。

，时限 。

---

• 括号序列合法的充要条件：

  将 设为 ， 设为 。括号序列 合法，当且仅当 的和为 且后缀和均非负。

先建立 SAM。

对于每个节点 ，求出任意一个 endpos ，设为 。

该节点代表着从 结尾的，开头在某区间 区间内的所有串。

我们要计数这些串中有几个是合法的。

• 后缀和非负

  右端点固定，不难发现左端点越靠前越有可能违反这个约束。

  所以，满足左端点起始点是一个区间。怎样求出这个区间呢？

  设原串的权值数组为 ，后缀和为 。 使用 ST 表维护，二分并查看区间最小值即可。

• 区间和为 0 变成区间数 的个数，std::vector 配合二分即可。

复杂度 。