题解：P17144 [NOI 2026] 木棉（暂无数据）

rabbit_mygo · 2026-07-26 15:34:28 · 题解

怎么没有单根号做法。

下面的转化如何得到的不赘述，详见其它题解。

一次询问是四元组 (l,r,x,y)，我们需要得到 x,y 会挂到的位置 px,py。定义 b_i 表示 i 在 [l,r) 中最后一次出现位置的后一位（没有出现就是 l），px 就是 b_x 后的第一个位置 p 满足 \sum_{j \le x}[b_j \le p] \le p-l+1。

发现 b 的变化只取决于 r，否则默认为 1 即可。

所以可以将询问刻画成二元组 (r,x)。而每次指针偏移一位带来的变化是 O(1) 的，莫队即可。然后我们分块，在块上二分即可做到 O(1) 修改 O(\sqrt n) 查询。

有个小细节是对于 x=r-l+1 的情况，你需要特殊处理 b_{r-l+1}。这个可以建一颗后缀主席树在上面二分。

视 n,m 同阶，时间复杂度 O(n \sqrt n+n \log n)。

代码

虽然但是，我做了大半场 t1，所以这题获得了 20 的高分（