【记录】暑假 8.25

xuyunao · 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)。