← 返回题目列表

Codeforces · 1958/G

G. 观测塔

中文机器翻译题面 查看原题

考虑 OX 轴从 $$$1$$$ 到 $$$n$$$ 的一段。该路段有 $$$k$$$ 观测塔。

每个塔都有两个参数 - 坐标 $$$x_i$$$ 和高度 $$$h_i$$$。所有塔的坐标都是不同的。从塔$$$i$$$,你可以看到点$$$j$$$,如果$$$|x_i - j| \le h_i$$$ (其中 $$$|a|$$$ 是 $$$a$$$ 的绝对值)。

一枚硬币可以将任何塔的高度增加 $$$1$$$。每个塔的高度可以增加任意次数(包括零)。

您需要处理 $$$q$$$ 独立查询。在第$$$i$$$查询中,给出了两个不同的点$$$l$$$和$$$r$$$。您需要计算能够看到这两个点(从一座塔或从不同塔)所需的最小硬币数量。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le n$$$) — OX 轴线段的长度和观测塔的数量。

第二行包含 $$$k$$$ 整数 $$$x_1, x_2, \dots, x_k$$$ ($$$1 \le x_i \le n$$$) — 观测塔的坐标。所有塔的坐标都是不同的。

第三行包含 $$$k$$$ 整数 $$$h_1, h_2, \dots, h_k$$$ ($$$0 \le h_i \le n$$$) — 观测塔的高度。

第四行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 查询数。

接下来的 $$$q$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l < r \le n$$$) - 下一个查询的描述。

输出

对于每个查询,输出一个整数 - 能够看到两个点(来自一个塔或来自不同塔)所需的最小硬币数量。

示例

输入 #1

20 3
2 15 10
6 2 0
3
1 20
10 11
3 4

输出 #1

3 1 0

输入 #2

10 2
2 9
1 2
3
4 5
5 6
1 10

输出 #2

2 2 0