← 返回题目列表

AtCoder · arc209_c

C. 调整矩形

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

分数: 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.