【APIO2018】新家
2021-01-31 01:14
标签：问题 定义 应该 最小 最小值 inf 数组 最大 pre 给定$n$个店铺的种类$t_i$、地点$x_i$和时间区间$[a_i..b_i]$。 询问某时某地的“便利度”，“便利度”定义为所有种类的距离最大值，种类的距离是该时间下，所有此类商店到该地点的距离最小值。 说实话，这个二分答案其实挺不好想的。（一开始看了题解，再回过头来看，才意识到这一点）。 我们可以从“最小的最大”窥伺出二分答案。 显然，我们可以想到离线，枚举时间的变化，用$set$维护$pre$数组，二分一个答案$mid$，就是查询$[x-mid..x+mid]$中有没有$k$个$pre 这个显然可以用主席树二维数点搞。 但是这样有个问题，虽然我们可以维护反的二元组$(pre_i,i)$，在值域上二分，把查询优化至一个$log$，但这样本身是要修改的，带修主席树就两个$log$了。 所以我们可以想想优化到一个$log$。 我们的询问不是数颜色，而是判断颜色个数是不是$k$，这应该可以一定程度上启发我们。（至此，我想到的就是这些） 直接查$[x+mid+1,INF]$的最小值是不是小于$[x-mid]$，如果小于，说明一种颜色跳过了区间，即此区间不合法。 这可是一个神奇的转换。 不用主席树了，直接上动态开点线段树维护区间最小值即可，查询的时候在值域上二分即可。 【APIO2018】新家 标签：问题 定义 应该 最小 最小值 inf 数组 最大 pre 原文地址：https://www.cnblogs.com/shxnb666/p/11632720.html题面：
题解：