CF1550F 题解

题意

传送门

数轴上顺次有 \(n\) 个点 \(a_1 < a_2 < \cdots < a_n\)。

有一只小青蛙，初始时在 \(a_s\) 处。小青蛙有两个参数：步长 \(d\) 和灵活程度 \(k\)。其中，步长 \(d\) 是确定的，而灵活程度 \(k\) 是可以调整的。

小青蛙可以从某个点跳到另一个点。但这是有要求的：小青蛙能从 \(a_i\) 跳到 \(a_j\)，当且仅当 \(d-k\leq |a_i-a_j|\leq d+k\)。

给定 \(a_1,...,a_n\) 和 \(d\)。你需要回答 \(q\) 次询问，每次询问给定一个灵活程度 \(k\) 和一个下标 \(i\)，你需要回答：此时的小青蛙能否跳到 \(a_i\)？

\(1\leq n,q\leq 2\times 10^5\)，\(1\leq s,i\leq n\)，\(1\leq a_i,d,k\leq 10^6\)，\(a_1 < a_2 < \cdots < a_n\)。

题解

借这题学习了整体二分。记一下。

发现答案有单调性，我们只需要对每个点求出能到达它的最小 \(k\)，就能 \(O(1)\) 回答。

对值域整体二分，设当前值域区间为 \([l,r]\)，考虑所有答案在 \([l,r]\) 的点。我们只需要将这些点分为 \([l,mid]\) 与 \((mid,r]\) 的两部分，递归解决即可。并由单调性，等价于根据 \(k=mid\) 时的可达与否分组。

此时答案在 \([0,l)\) 的点已经存在，利用他们更新 \(k=mid\) 时能跳到的点。

待考虑的点有两种方式更新：1. 由 \([0,l)\) 的一步跳到；2. 由第一种点跳到。第一种用 set 即可；第二种可以用队列和 set（类似广搜）。这样的方式可以保证 \(O(n \log^2 n)\) 的复杂度。