HMF-have much fun Site
文章
标签
16
联系方式戳我~
阅
【题解】CF1625E1 Cats on the Upgrade (easy version)
热度: loading...
在打模拟赛的时候写题解好刺激啊
首先考虑不包含嵌套关系的括号序列选取，那这个问题就变成了从一个序列中选取一个非空子段的方案数，为 种。
考虑有嵌套关系的括号序列，同层（即互相没有嵌套关系）的括号按照上面所说的方式选取。若选取一个括号，则被这个括号包含的一整段括号序列必须全部选取，因此不同层的括号之间不互相影响，可以分开考虑。
考虑如何统计每一层的贡献。用栈匹配括号，观察到一个右括号对应的左括号，这个左括号的左边要么是右括号，即为同层括号，要么是左括号，即为包含自己的括号。因此我们在右括号的位置上记 表示同层的括号中，以这个括号为右端点，能选取几段非空子段。设 位置的右括号对应的左括号的位置为 ，则 。选取这一层括号的总贡献即为这一层括号的 之和。
考虑询问。询问的区间是一段合法括号，因此直接统计 之和即可。询问区间的 之和可以很简单地用前缀和求出来，这里注意一点由于询问区间内的不一定是同层的所有括号，因此要减去 。至此题目圆满完成。
赏
