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 翻译