题解：P4477 [BJWC2018] 基础匹配算法练习题

KidA · 2025-04-23 20:25:19 · 题解

只有询问无修改，于是考虑莫队维护 b_i。

容易发现对于每个 b_i，它可以匹配的 a_i 总是一个从 1 开始的连续区间。采用贪心的思想，我们对于每个 b_i，我们尽量选择最大的那个 a_i，称其为它的「最佳位置」。

对于这种连续区间，我们考虑使用线段树维护之。维护三个信息：

• 答案 ans；

• 匹配成功的 b_i 区间大小 bsiz。

具体而言：

• 增加：尽可能地向右子树寻找 a_i 以使得 a_i 最大化，若最后匹配得了且是「最佳位置」，那么令 ans+1，bsiz+1；

• 删除：最后若 b_i 先前有匹配，则令 ans-1，bsiz-1。

pushup 时：

综上，本题是莫队与线段树的结合，其中莫队为整体框架，线段树处理寻找匹配与计算贡献的问题，并且让我们学会了只有询问考虑莫队、以及连续区间问题考虑线段树的技巧。时间复杂度 O(Q \sqrt{m} \log n)，代码，需要快读。