CF1340F Nastya and CBS

题意：你需要动态维护一个多种括号组成的，长度为 的括号序列。需要支持两种操作：

• 单点修改

• 查询 区间是否是一个合法的括号序列。

，时限 ，空限 。

---

先考虑如何暴力回答单组询问。

用栈维护括号序列的匹配。若出现左括号，加入栈中。若出现右括号，查看栈顶是否为同类，若是，则弹栈，若不是（或栈为空），失配。

分块

对于每个块内，跑一次括号匹配。

此处允许栈为空的情况，此时要将右括号加入栈中。

若匹配时内部已经出现了失配，则对该块打上标记。

若没有失配，最终剩下的括号形如 ，左边是一系列右括号，右边是一系列左括号。

回答询问时，将散块和整块的括号用栈再跑一次匹配。

先把散块按类似整块的方法整理。于是现在有若干段 “右右右左左左” 的括号序列等待合并。

这要求第 组的左括号与第 组的右括号完全匹配。使用 加速检验，复杂度可以做到 。

（兔队）线段树

对于每个线段树节点，维护内部匹配完之后剩下的括号，以及失配标记。

记左侧的右括号为 ，右侧的左括号为 。为了方便维护，我们可以将 翻转。

记要合并的两个点为 。考虑 ，不妨设 的长度较小，则将 抵消一部分，然后 剩余的一部分配上 为新的 ，原来的 即为 。

于是，我们在合并时需要查询 前 个位置的 值。

记 表示 长度为 的前缀的 值。

若 或者 可以直接返回结果。

否则，观察 是怎样得来的。

• 这时 ，直接递归右儿子。

• 这时 。

  若 ，直接递归左儿子。

  若 ，则查询 ，然后左侧加上 。

综上， 的复杂度为 ，每次操作的复杂度也就是 的。

询问时需要将拆分出的节点用栈记录，特殊写一个 。