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

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

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

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

具体而言：

pushup 时：

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