AT_arc209_c.[ARC209C] Adjusting a Rectangle

给定正整数 $N$、$X$ 以及长度为 $N$ 的整数序列 $S = (S_1, S_2, \dots, S_N)$、$P = (P_1, P_2, \dots, P_N)$。其中每个 $P_i$ 的值为 $1$ 或 $-1$。

你会收到 $Q$ 个询问。每个询问给定整数 $l, r$，满足 $1 \leq l \leq r \leq N$，你需要进行如下的游戏：

• 初始时，你的得分为 $0$，整数 $a, b$ 被初始化为 $a = 1, b = 1$。
• 对于 $i$ 从 $l$ 到 $r$，依次进行如下操作：
  • 如果 $i$ 是偶数，可以将 $a$ 的值替换为 $1$ 到 $X$ 间的任意整数；如果 $i$ 是奇数，可以将 $b$ 的值替换为 $1$ 到 $X$ 间的任意整数。
  • 之后，如果 $ab \geq S_i$，则将 $P_i$ 加入到你的得分中。否则，得分不变。注意，$P_i$ 可能为负数。

对于每个询问，求游戏结束时你分数可能达到的最大值。

输入将由标准输入给出，格式如下：

$N\ X\ Q$
$S_1\ S_2\ \ldots\ S_N$
$P_1\ P_2\ \ldots\ P_N$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

每个查询格式如下：

$l\ r$

输出共 $Q$ 行。

第 $i$ 行输出第 $i$ 个查询下，游戏结束时你能达到的最大分数。

样例解释 1

对于第一个查询，通过如下方案，游戏结束时可以获得 $2$ 分：

$i$	操作	$a$	$b$	得分
5	替换 $b=4$	1	4	0
6	替换 $a=2$	2	4	1
7	替换 $b=3$	2	3	0
8	替换 $a=4$	4	3	1
9	替换 $b=4$	4	4	2

每一步：

• 第 $5$ 步，$ab=4 < S_5(=5)$，得分不变。
• 第 $6$ 步，$ab=8 \geq S_6(=7)$，得分加 $P_6(=1)$。
• 第 $7$ 步，$ab=6 \geq S_7(=3)$，得分加 $P_7(=-1)$。
• 第 $8$ 步，$ab=12 \geq S_8(=9)$，得分加 $P_8(=1)$。
• 第 $9$ 步，$ab=16 \geq S_9(=16)$，得分加 $P_9(=1)$。

最终得分为 $2$，无法达到 $3$ 分或更高，因此输出 $2$。

数据范围

• $1 \le N, X, Q \le 10^5$
• $1 \le S_i \le 10^5$
• $P_i = 1$ 或 $P_i = -1$
• 对于每个查询，$1 \le l \le r \le N$
• 所有输入均为整数。

由 ChatGPT 5 翻译