AT_arc163_b [ARC163B] Favorite Game 题解

_32_qwq · 2023-07-03 17:39:24 · 题解

题面

令值域为 V。

因为我们为了使一个元素进入区间，我们可以增加这个区间，或者移动这个元素，但是显然增加区间的时候可能会有其它元素加入这个区间，所以改变区间应该会更优。于是，贪心地，我们只改变区间的左右端点。

容易想到枚举左右端点，然后判断这个答案是否是满足 \ge M 的，如果是，那么就和答案取 \min，时间复杂度是 O(nV^2)。显然不行，考虑优化。

• 首先，可以想到一个区间内元素的数量可以使用权值线段树维护，本题数据范围是 10^9，所以要考虑动态开点。

• 其次，对于同一个左端点，显然我们需要的是最小的可行的右端点，并且比这个右端点更小的都不行，比这个右端点更大的都可行，所以右端点的选取是具有单调性的，于是可以考虑二分。

• 最后，左端点显然需要正好选到元素上或者不变，所以我们枚举左端点的时候只需要枚举元素，而不需要枚举值。

时间复杂度 O(n\log^2V)，常数比较大（其实这个算法复杂度本身就比较大），不打快读好像过不了。（好像打了也不一定能过）

code