自动搬运

查看原文

来自洛谷，原作者为

	qwaszx 不再为往事受困.

搬运于2025-08-24 22:23:54，当前版本为作者最后更新于2020-08-27 21:10:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先看数据范围知道应该不是根号，考虑polylog

首先假装没有操作3，那么考虑线段树. 每个区间的括号合并完成后应该形如 "))))(((("，考虑怎么合并两个儿子的信息，不失一般性，设左儿子的 "(" 数量多于右儿子的 ")" 数量，其它的情况类似. 那么匹配完成后分为三部分，左儿子的 "))))"，左儿子的 "(" 和右儿子的 ")" 匹配之后左儿子剩下的 "(("，右儿子的 "((((". 假如我们分别维护了 "))))" 和 "((((" 对应的信息，那么我们只需要考虑中间的部分如何维护.

考虑中间的部分相当于在计算左儿子的前若干个 "(" 的信息，于是实现函数 solve(u,K) 表示计算节点 $u$ 的前 $K$ 个 "(" 的信息. 考虑 $u$ 的两个儿子的情况，如果右儿子的 ")" 不少于左儿子的 "("，那么意味着左儿子的 "(" 不会造成贡献，递归到 solve(rson[u],K). 否则，设左儿子的 "(" 个数比右儿子的 ")" 个数多 $t$，那么如果 $K\leq t$，那么全部由左儿子贡献，递归到 solve(lson[u],K)；否则，贡献由中间剩余的 "(" 和右儿子的 solve(rson[u],K-t) 合并得到，由于中间剩余的 "(" 我们已经维护出来了，所以只需要递归右边. 于是每次只需要向一边递归，复杂度 $O(\log n)$.

还有一个问题是两个简单信息如何合并，对于 $\max$ 而言合并是平凡的，对于 NAND 似乎并没有什么好的性质，于是按照 此题 的做法，对每一位维护 0/1 经过该区间之后会变成什么，利用位运算做到 $O(1)$ 合并.

于是现在我们可以在 $O(\log n)$ 的时间内完成一次 pushup，一次线段树操作会涉及到 $O(\log n)$ 个节点的 pushup，所以线段树的复杂度为 $O(n\log n+m\log^2 n)$.

那么3操作显然使用平衡树维护，由于上面的 pushup 的复杂度为树深度，所以需要找一个树深度正确的平衡树，fhq treap 和 WBLT 应该均可，我用的是类似线段树的虚假的 WBLT，我的写法需要卡常数（当然为了方便没有很仔细地卡），一些细节在注释中了.

upd:经过提醒，建树部分复杂度为 $T(n)=2T(n/2)+O(\log n)=O(n)$

upd2:lxl觉得抄题解壬太多力 所以把代码去了 需要代码的话可以直接私信我