题解：AT_abc389_f [ABC389F] Rated Range

lovely_nst · 2025-01-19 08:31:46 · 题解

AT_abc389_f [ABC389F] RG

前置

1. 线段树 + 二分

2. 平衡树

正文

方法一（线段树）

将所有询问离线下来并排序，记为数组 a。可证得在操作中 a 满足单调不降性。

证明：操作 [l,r] 只会对 [l,r] 范围内的 a_i 加一，修改后最大只能到 r + 1。若原本 a_i>r，那就一定满足 a_i\ge r+1，一定排在修改为的后面；若原本 a_i<l，那一定排在修改位的前面。因为原数组满足单调不降性，因此修改后也满足。

将 a 放入线段树，线段树维护区间最小值，最大值，每次通过二分（因为单调不降）找到满足 l\le a_x \le r 的所有 x 并加一。时间复杂度 O(n\log^2 n)。

方法二（平衡树）

用 FHQ_Treap 实现值分裂，将 [l,r] 的节点打上标记，在分裂和合并时下传标记。时间复杂度 O(n\log n)。