\(O((N + Q)\log(N)))\) で解くことができます。

\(A\) がソートされているとします。

各クエリに対して、以下の条件を満たす整数 \(i\) を求めます。

• \(A_{i} < b\) かつ、\(b - A_{i} > A_{i + k - 1} - b\) かつ、\(b - A_{i + 1} \leq A_{i + k} - b\)

\(A\) に適当な番兵を追加することで、このような \(i\) は必ず存在することができます。 また、このような \(i\) は \(1\) つしか存在しませんし、二分探索をすることで時間計算量 \(O(\log(N))\) で求められます。

そのような \(i\) に対して、以下が成り立ちます。

• \(i < j < i + k \) ならば、 \(|A_{j} - b| \leq \min(|A_{i} -b|, |A_{i + k} - b|)\)
• \(j < i\) または \(i + k < j\) ならば、 \(|A_{j} - b| \geq \min(|A_{i} -b|, |A_{i + k} - b|)\)

\(i < j < i + k \) を満たす \(j\) は \(k - 1\) 個であることから、答えは \(\min(|A_{i} -b|, |A_{i + k} - b|)\) となります。

クエリごとに時間計算量 \(O(\log(N))\) で解けるため、全体の時間計算量は \(O((N + Q)\log(N))\) で解けます。

実装例 C++