Luogu7044 「MCOI-03」括号

发表于 2025-02-25 更新于 2025-02-26 分类于算法竞赛，题，洛谷阅读次数：

题意：定义一个括号串的级偏值为将该括号串修改为合法括号串需要的最小操作数。

在某次操作中，可以添加或删除一个括号。

定义一个括号串的级偏值为该串所有子串的级偏值之和。

现在你需要求出一个长度为的括号串的级偏值。答案对取模。

，时限。

首先考虑如何求出某个括号串的级编值。

显然，将该括号串中的括号对尽力抵消，最终会剩下 )))(( 的形式，此时操作次数即为剩下的括号个数。

设子串的级编值为。

等级编值的本质只是对每个子串的级偏值进行了线性组合。

具体地，考虑的贡献系数，即为选择次子区间从缩小为的方案数。

可以对左右端点分别考虑。对于左端点，方案数为在长为的区域内选个单调不降数，最后选到。即为将拆分成个自然数的方案数。右端点类似。

于是可以写出答案：

考虑序列扫描线，在逐渐增大的同时维护每个的贡献，即对每个计算

维护表示子串消除后得到的括号序列中右括号和左括号的个数，即 $共个共个$

当在末尾加入一个括号时（增大时），容易计算新的括号表示：

综上，只有且加入时，才会使得减一，否则都是加一。

于是，使用线段树维护的最小值以及最小值贡献系数和即可。复杂度为。

然而这个做法还是太过丑陋了……

从右到左匹配，记录每个右括号匹配到的左括号。

当指针经过一个有配偶的右括号时，查看与其配对的左括号，则的的化简结果减少了一个左括号，其余的没有减少。

这就容易维护了。