本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-25 09:43:45

CF3D Least Cost Bracket Sequence

首先考虑全是 ? 怎么做，考虑括号序列合法的条件，假设最开始全是 )，在奇数的位置选择一个变成 (。

或者把 ( 看作 $1$，) 看作 $-1$，对于每个位置前缀和非负。

假设最初全都是左括号，用堆维护出从右括号变成左括号的贡献，也就是 $a_i - b_i$ 的最小值，每次加上即可。

CF911G Mass Change Queries

考虑对操作换维，从按照时间维度进行操作变为按照序列维度或按照颜色维度。

按照序列维度，考虑维护 $100$ 个 tag，每次 $O(100)$ 维护线段树，最后查询，复杂度 $O(n \log n)$。

按照颜色维度，对于每个颜色维护，维护颜色为该颜色的位置，维护成 $0/1$，每次线段树分裂合并，复杂度 $O(n \log n)$。