P4632 Solution
对时间扫描线,就变成支持单点加入删除一个颜色点,求所有颜色距离某个点的距离最大值。
考虑二分答案,现在就是要检验 \([x-mid,x+mid]\) 内是否有 \(1\sim k\) 颜色的点各至少一个。
数颜色可以考虑维护 \(pre_i\) 表示上一个与该点同色的位置。然后区间 \([l,r]\) 出现过所有颜色,等价于 \([r+1,+\infty)\) 的所有 \(pre\) 大于等于 \(l\);否则如果存在一个 \(pre<l\),则说明这个颜色在区间中没出现过。
这里我们在 \(0,10^8+1\) 位置加 \(1\sim k\) 的颜色点各一个。就不用讨论了。。
\(pre\) 可以用 multiset
维护某个颜色的所有点,求前驱后继可以将插入删除变为 \(\Theta(1)\) 次 \(pre\) 的修改。
二分后查询一下 \((x+mid,+\infty)\) 的 \(pre\) 最小值。值域大,动态开点线段树维护即可。
这样复杂度是 \(\Theta(n\log^2n)\) 的。发现可以线段树二分,于是复杂度可以降到 \(\Theta(n\log n)\)。
有很多细节,首先某一时刻一个位置会有多个颜色的点,甚至可能有多个同颜色的点。
所以对于线段树的叶子要维护一个 multiset
搞这里的所有点。还有 multiset
删除要用 lower_bound
。
线段树二分的话,要注意最后 l==r
返回时判一下是否等于 \(10^8+1\),然后以此看看是否有解,有解的话要用 x-t[o].mn
计算。
这是因为我们的区间右端点对 \(10^8+1\) 取了 \(\min\),可能会有超出去但左端点不超的而情况。
标签:p4632,pre,颜色,线段,solution,multiset,Theta,二分 From: https://www.cnblogs.com/iorit/p/18052647