AdditionalFile4148.zip

#4148. 「JOISC 2024 Day1」鱼 3

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOISC 2024 Day1 T1 「魚 3 / Fish 3」

JOI 君在一个大型水箱养了 $N$ 条鱼，并且对所有鱼从 $1$ 到 $N$ 编号。

JOI 君有足量的两种饲料 A 和 B，每次投放一片饲料后，有且仅有一条鱼会吃它。根据饲料类型，会对鱼的智力产生不同效果：

• 鱼 $k\enspace (1\le k\le N)$ 吃了一片饲料 A 之后，鱼 $k$ 的智力增加 $D$。
• 鱼 $k\enspace (1\le k\le N)$ 吃了一片饲料 B 之后，鱼 $k$ 和所有编号大于 $k$ 的鱼的智力各增加 $1$。

目前所有鱼的智力均为 $0$。JOI 君希望鱼 $i\enspace (1\le i\le N)$ 的智力等于预期值 $C_i$，但这不一定能做到。

他考虑了 $Q$ 个问题。其中第 $j\enspace (1\le j\le Q)$ 个问题形如：

• 从初始状态（即所有鱼的智力均为 $0$）开始，依次投放若干片饲料（可以不投放任何饲料），并可以指定吃每一片饲料的鱼，是否可能使鱼 $L_j, L_j+1,\dots, R_j$ 的智力均和预期值 $C$ 一致？如果可以，请给出至少要投放多少片饲料 A。

给定鱼、饲料和询问信息，写一个程序求解询问。

输入格式

从标准输入读入以下内容：

$$\begin{align} & N\enspace D\\ & C_1\enspace C_2\enspace\cdots\enspace C_N \\ & Q \\ & L_1\enspace R_1 \\ & L_2\enspace R_2 \\ & \vdots \\ & L_Q\enspace R_Q \end{align}$$

输出格式

输出 $Q$ 行，每行一个整数，对于其中第 $j\enspace (1\le j\le Q)$ 行，若鱼 $L_j,L_j+1,\dots ,R_j$ 可以同时恰好达到预期的智力值，输出最少需要投放的饲料 A 的片数；否则输出 -1。

样例 1

输入

4 2
3 1 2 1
1
1 3

输出

1

经过以下操作，鱼 $1,\,2,\,3$ 最终均可达到预期的智力值，且仅需要 $1$ 片饲料 A。

• 鱼 $1,\,2,\,3,\,4$ 的智力依次分别为 $0,\,0,\,0,\,0$。
• JOI 君首先投放一片饲料 B，鱼 $3$ 吃了之后，四条鱼的智力依次为 $0,\,0,\,1,\,1$。
• 投放一片饲料 A，鱼 $1$ 吃了之后，四条鱼的智力依次为 $2,\,0,\,1,\,1$。
• 最后投放一片饲料 B，鱼 $1$ 吃了之后，四条鱼的智力分别为 $3,\,1,\,2,\,2$。

由于不投放任何饲料 A 无法使鱼 $1,\,2,\,3$ 分别恰好达到智力值 $1,\,2,\,3$，因此输出 $1$。

这组样例满足子任务 $1,\,5$ 的限制。

样例 2

输入

4 2
0 1 0 1
3
1 2
2 3
1 1

输出

0
-1
0

这组样例满足子任务 $1,\,2,\,5$ 的限制。

样例 3

输入

5 1
3 1 4 1 5
3
1 5
2 4
3 5

输出

5
3
3

这组样例满足子任务 $1,\,3,\,5$ 的限制。

样例 4

输入

6 3
16 14 13 8 6 5
4
1 4
2 5
3 3
1 6

输出

9
8
0
-1

这组样例满足子任务 $1,\,4,\,5$ 的限制。

数据范围与提示

对于所有数据，满足：

• $1\le N\le 300\,000$
• $1\le Q\le 300\,000$
• $1\le D\le 10^{12}$
• $0\le C_i\le 10^{12}\enspace (1\le i\le N)$
• $1\le L_j\le R_j\le N\enspace (1\le j\le Q)$
• 所有输入的数均为整数。

详细子任务附加限制及分值如下表所示：

子任务编号	附加限制	分值
$1$	$N \le 3\,000,\enspace Q \le 3\,000$	$9$
$2$	$C_i\le 1\enspace (1\le i\le N)$	$7$
$3$	$D=1$	$28$
$4$	$C_i\ge C_{i+1}\enspace (1\le i\le N-1)$	$20$
$5$	无附加限制	$36$