主席树是什么.jpg

迟暮天复明 · 2025-12-03 17:52:24 · 题解

AC time: about 38 mins, +.

考虑暴力法。

用普通线段树维护区间极小可以覆盖所有区间内集合的线段。pushup 的时候直接暴力遍历每一边的极小线段集合，设遍历到了 [l,r]，那么在另一边找到一条线段 [l',r'] 使得 l\le l' 且 r' 最小即可。这个可以直接维护后缀 min。不难证明使用这个方法可以找到扩充出来的所有线段。

时间复杂度：考虑线段树上每一个结点里存储的线段最坏情况下是它底部叶子里所有的原始线段均扩充出来一条线段。因此，原始集合中每一条线段在线段树上最多出现 \log n 次。而 pushup 的时候对于每一条线段需要进行一次二分。所以 build 总时间复杂度就是 O(n\log n\log k) 的。那么加上询问后时间复杂度就应该是 O((n+m)\log n\log k)。可以通过此题。

submission