3 條題解
資訊
- ID
- 277
- 時間
- 3000ms
- 記憶體
- 512MiB
- 難度
- 8
- 标签
- (無)
- 遞交數
- 29
- 已通過
- 6
- 上傳者
没参加比赛,过来口胡一下。
先假设可以离线。
对右端点 r 进行扫描线,在每个元素最后一次出现处标记上其信息,否则不标记。
然后就是查询从 l 到当前末尾被标记的元素的第 k 小值。
也就是 2-side 矩形查询 k 小值。
我们用权值线段树套位置的线段树,直接在其上二分即可;注意内层树要动态开点。
由于本题强制在线,不能扫描线,我们直接对树套树可持久化一下即可。
时间复杂度 O((n+q)log2n),空间复杂度 O(nlog2n);内层使用可持久化平衡树(应该?)就可以做到 O(nlogn) 空间了。
这题为啥正解是分块啊,怎么回事。