分数: 900 点
问题陈述
给你正整数 N, X 和长度的整数序列 N: S = (S_1, S_2, \dots, S_N), P = (P_1, P_2, \dots, P_N)。 这里,每个元素 P is 1 or -1.
你被给予 Q 查询。在每个查询中,您都会得到整数 l, r 满意 1 \leq l \leq r \leq N,并且您玩以下游戏:
- 最初,您的分数是 0和整数 a, b 初始化为 a = 1, b = 1.
- 对于 i = l, l+1, \dots, r 按此顺序,执行以下操作:
- If i 为偶数,替换 的值 a 之间的任意整数 1 和 X (含);如果 i 为奇数,替换为 b 之间的任意整数 1 和 X (含)。
- 之后,如果 ab \geq S_i,添加 P_i 给你的分数。否则,分数不会改变。请注意 P_i 可以为负数。
对于每个查询,找到游戏结束时得分的最大可能值。
约束
- 1 \le N, X, Q \le 10^5
- 1 \le S_i \le 10^5
- P_i = 1 or P_i = -1.
- 对于每个查询, 1 \le l \le r \le N.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
9 4 4 3 11 10 12 5 7 3 9 16 1 1 -1 1 -1 1 -1 1 1 5 9 1 4 5 5 2 8
示例输出 1
2 3 0 1
在第一个查询中,可以做出分数 2 当游戏通过以下程序结束时:
| i | 操作 | a | b | 分数 |
|---|---|---|---|---|
| - | 1 | 1 | 0 | |
| 5 | 替换值 b 与 4。自从 ab < S_5 \, (= 5),分数没有变化。 | 1 | 4 | 0 |
| 6 | 替换值 a 与 2。自从 ab \geq S_6 \, (= 7),添加 P_6 \, (= 1) 到分数。 | 2 | 4 | 1 |
| 7 | 替换值 b 与 3。自从 ab \geq S_7 \, (= 3),添加 P_7 \, (= -1) 到分数。 | 2 | 3 | 0 |
| 8 | 替换值 a 与 4。自从 ab \geq S_8 \, (= 9),添加 P_8 \, (= 1) 到分数。 | 4 | 3 | 1 |
| 9 | 替换值 b 与 4。自从 ab \geq S_9 \, (= 16),添加 P_9 \, (= 1) 到分数。 | 4 | 4 | 2 |
不可能得分 游戏结束时 3 或更多,所以输出 2.