AT_joigsp2025_k ういろう (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, \dots, 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.（7 分）$N \leq 20$，$Q \leq 20$。 2.（11 分）$N \leq 300$，$Q \leq 20$。 3.（15 分）$N \leq 5\,000$，$Q \leq 20$。 4.（24 分）$Q \leq 20$。 5.（21 分）$A_i \leq 2$（$1 \leq i \leq N$）。 6.（14 分）$A_i \leq 20$（$1 \leq i \leq N$）。 7.（8 分）无其他限制。 --- ## 样例解释 1 第 $1$ 次游戏可能如下： - 首先在黑板写 $0$。 - 然后将卡片 $1,2,3$ 按顺序排列。 - 当前黑板上的数为 $0$，第 $1$ 张卡片上的数为 $3$。将黑板改写为 $3$。 - 当前黑板上的数为 $3$，第 $2$ 张卡片上的数为 $4$。将黑板改写为 $7$。 - 当前黑板上的数为 $7$，第 $3$ 张卡片上的数为 $7$。将黑板改写为 $0$，并吃掉 $1$ 个ういろう。 此时，第 $1$ 次游戏最多能吃 $1$ 个ういろう，提高到 $2$ 个是不可能的。因此输出 $1$。 第 $2$ 次游戏可能如下： - 首先在黑板写 $0$。 - 然后排列卡片 $4$。 - 当前黑板上的数为 $0$，第 $4$ 张卡片上的数为 $2$。将黑板改写为 $2$。 此时，第 $2$ 次游戏最多能吃 $0$ 个ういろう，不可能更高。因此输出 $0$。 此输入样例满足子任务 $1,2,3,4,6,7$ 的约束。 --- ## 样例解释 2 第 $1$ 次游戏可能如下： - 首先在黑板写 $0$。 - 然后排列卡片 $1,2$。 - 当前黑板上的数为 $0$，第 $1$ 张卡片上的数为 $1$。将黑板改写为 $1$。 - 当前黑板上的数为 $1$，第 $2$ 张卡片上的数为 $2$。将黑板改写为 $3$。 此时，第 $1$ 次游戏最多能吃 $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 翻译