题解：P11750 「TPOI-1D」谢谢您。

wang54321 · 2025-02-19 09:36:09 · 题解

场上不会根号分治，考虑序列分块。

下文默认 n,m,k 同阶。

对区间进行分块，设块长为 B 考虑每一块的答案如何处理。

容易发现每个区间的答案是可差分信息，在 vector 上二分即可 O(\log n) 处理单个区间的贡献，对于 每一块：拆分成 O(n) 个全局询问，因为询问是全局的，把块内每个区间的 l 挂到 r 上，取后缀 \min，扫描线，插入一个数的时候更新等于这个数的答案就好了，由于每次查询要在 vector 上二分，是 O(n\log n+n\frac{n}{B}) 的，注意这里暴力处理每个颜色的值的话空间会爆炸，询问的时候对 k 扫描线，每次重新预处理一遍就好了。

之后对每个询问暴力合并散块就是 O(nB\log n) 的，考虑优化，这种题里面二分通常能优化成分散层叠或者分块状物，直接用 O(\sqrt n)-O(1) 维护前缀和的分块即可做到 O(nB)。