AT_joisp2025_l ういろう (Uiro)

葵有 $N$ 张卡片，每张卡片编号为 $1$ 到 $N$。每张卡片上写有一个正整数，对于卡片 $i$（$1 \leq i \leq N$），上面的整数为 $A_i$。 葵会用卡片和黑板玩 $Q$ 次游戏。第 $j$ 次游戏（$1 \leq j \leq Q$）的规则如下： - 在黑板上写下 $0$。 - 在桌上依次从左到右排列编号为 $L_j, L_j+1, \ldots, R_j$ 的卡片。 - 按照以下方式进行 $R_j - L_j + 1$ 次操作。第 $k$ 次操作（$1 \leq k \leq R_j - L_j + 1$）规则如下： - 设当前黑板上的整数为 $x$，桌面上从左往右排的第 $k$ 张卡片上的数字为 $y$。擦掉黑板上的 $x$，将 $x + y$ 或 $x - y$ 写到黑板上。如果选择写 $x - y$，就吃 1 个“ういろう”（和菓子）。 - 但是，不能在黑板上写一个小于 $0$ 的整数。 你的任务是，对于每一次游戏，求葵最多能吃到多少个ういろう。 给定卡片和每次游戏的信息，请编写程序，计算每次游戏葵最多能吃到多少个ういろう。

输入按照以下格式： > $N$ > $A_1\ A_2\ \cdots\ A_N$ > $Q$ > $L_1\ R_1$ > $L_2\ R_2$ > $\vdots$ > $L_Q\ R_Q$

输出 $Q$ 行。第 $j$ 行（$1 \leq j \leq Q$）输出第 $j$ 次游戏葵最多能吃到的ういろう的个数。

## 子任务 1.（3 分）$N \leq 20$，$Q \leq 20$。 2.（5 分）$N \leq 300$，$Q \leq 20$。 3.（7 分）$N \leq 5\,000$，$Q \leq 20$。 4.（15 分）$Q \leq 20$。 5.（21 分）$A_i \leq 2$（$1 \leq i \leq N$）。 6.（29 分）$A_i \leq 20$（$1 \leq i \leq N$）。 7.（20 分）无其他额外限制。 --- ## 样例解释 1 第一次游戏可以如下进行： - 首先，黑板上写 $0$。 - 然后，将卡片 $1, 2, 3$ 依次从左到右排列。 - 当前黑板上的数为 $0$，第 1 张卡片上的数为 $3$，擦掉 $0$，写下 $3$。 - 当前黑板上的数为 $3$，第 2 张卡片上的数为 $4$，擦掉 $3$，写下 $7$。 - 当前黑板上的数为 $7$，第 3 张卡片上的数为 $7$，擦掉 $7$，写下 $0$，吃 1 个ういろう。 此时本次游戏中吃到ういろう的数量为 1，且不能超过 1。因此，输出 1。 第二次游戏如下： - 首先，黑板上写 $0$。 - 然后，将卡片 $4$ 排列在桌上。 - 当前黑板上的数为 $0$，第 1 张卡片上的数为 $2$，擦掉 $0$，写下 $2$。 此时本次游戏中吃到ういろう的数量为 0，且不能超过 0。因此，输出 0。 本输入样例满足子任务 1, 2, 3, 4, 6, 7 的限制。 --- ## 样例解释 2 第一次游戏可以如下进行： - 首先，黑板上写 $0$。 - 然后，将卡片 $1, 2$ 依次从左到右排列。 - 当前黑板上的数为 $0$，第 1 张卡片上的数为 $1$，擦掉 $0$，写下 $1$。 - 当前黑板上的数为 $1$，第 2 张卡片上的数为 $2$，擦掉 $1$，写下 $3$。 此时本次游戏中吃到ういろう的数量为 0，且不能超过 0。因此，输出 0。 本输入样例满足所有子任务限制。 --- ## 样例解释 3 本输入样例满足子任务 1, 2, 3, 4, 7 的限制。 # 数据范围 - $1 \leq N \leq 200\,000$。 - $1 \leq A_i \leq 100$（$1 \leq i \leq N$）。 - $1 \leq Q \leq 200\,000$。 - $1 \leq L_j \leq R_j \leq N$（$1 \leq j \leq Q$）。 - 所有输入都是整数。 由 ChatGPT 5 翻译