CF1039E Summer Oenothera Exhibition

有些人喜欢花时间参加编程竞赛，而 Dina 更喜欢拍摄美丽的照片。当 Byteland 植物园宣布举办夏季月见草展览时，她决定带着新相机去那里试试。 展览由 $l = 10^{100}$ 种月见草排成一排，按顺序编号为 $0$ 到 $l - 1$。相机镜头一次可以拍摄 $w$ 种花，也就是说，Dina 可以拍摄编号从 $x$ 到 $x + w - 1$ 的花（$x$ 是 $0$ 到 $l - w$ 之间的整数）。我们用 $[x, x + w - 1]$ 表示这样的一张照片。 她一共拍摄了 $n$ 张照片，第 $i$ 张（按时间顺序）是 $[x_i, x_i + w - 1]$。她发现月见草的花朵在傍晚开放后，决定用这些照片制作延时视频。 Dina 会对每张照片进行裁剪，保留其中恰好包含 $k$ 朵花的一个区间，然后按原顺序将这些照片合成视频，最终创作出一部美丽的艺术作品！ 一个“场景”是指一段连续的照片，这些照片中包含的花的集合完全相同。两个场景之间的变化称为“切换”。例如，第一张照片包含 $[1, 5]$ 的花，第二张包含 $[3, 7]$，第三张包含 $[8, 12]$。如果 $k = 3$，Dina 可以将第一、二张照片裁剪为 $[3, 5]$，第三张裁剪为 $[9, 11]$。前两张照片构成一个场景，第三张照片构成另一个场景，第二、三张照片之间发生了一次切换。如果 $k = 4$，那么每两张照片之间都必须切换。 Dina 希望切换的次数尽可能少。请你帮她计算，对于不同的 $k$，最少需要多少次切换。

第一行包含三个正整数 $n$、$w$、$q$（$1 \leq n, q \leq 100\,000$，$1 \leq w \leq 10^9$）——照片数量、每张照片包含的花的数量、询问的数量。 第二行包含 $n$ 个非负整数 $x_i$（$0 \le x_i \le 10^9$）——每张照片最左侧花的编号。 第三行包含 $q$ 个正整数 $k_i$（$1 \le k_i \le w$）——每个询问对应的裁剪宽度 $k$。 保证所有 $k_i$ 互不相同。

输出 $q$ 个整数，依次表示对于每个裁剪宽度 $k_i$，最少需要的切换次数。

由 ChatGPT 4.1 翻译