题解 P6781 【[Ynoi2008]rupq】

· · 题解

首先看数据范围知道应该不是根号，考虑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觉得抄题解壬太多力 所以把代码去了 需要代码的话可以直接私信我