P10430 [JOISC 2024] 鱼 3 (Day1)

JOI 君在一个大水缸中饲养着 $ N $ 条鱼，每条鱼的编号从 $ 1 $ 到 $ N $。 JOI 君有两种类型的鱼食，$ A $ 和 $ B $，两种都有足够的数量。当往水族箱中添加一块食物时，恰好有一条鱼吃掉它（任何鱼都可以吃掉它），并且根据食物的类型以及吃掉它的鱼的情况，鱼的智力变化如下： - 当第 $ k $ 条鱼（$ 1 \leq k \leq N $）吃掉一块 $ A $ 型食物时，第 $ k $ 条鱼的智力恰好增加 $ D $。 - 当第 $ k $ 条鱼（$ 1 \leq k \leq N $）吃掉一块 $ B $ 型食物时，编号大于等于 $ k $ 的所有鱼的智力都恰好增加 $ 1 $。 目前，所有鱼的智力都为 $ 0 $。JOI 君希望使第 $ i $ 条鱼（$ 1 \leq i \leq N $）的智力等于其理想智力 $ C_i $，但这并不总是可能的。 因此，他考虑了 $ Q $ 个问题。第 $ j $ 个问题（$ 1 \leq j \leq Q $）如下： - 从所有鱼的智力都为 0 的状态开始，通过重复将食物放入水族箱零次或多次的动作，是否可能达到所有鱼 $ L_j , L_j + 1 ,..., R_j $ 都拥有其精确的理想智力值的状态？此外，如果可能，需要放入水族箱的 A 型食物的最小数量是多少？ 编写一个程序，给定有关 JOI 君的鱼的信息以及有关问题的信息，回答他的问题。

无

无

#### 样例解释 1 例如，在以下情况下，所有鱼 $1,2,3$ 最终都达到了其精确的理想智力值，且放入水族箱的 $A$ 型食物的数量为 $1$。 - 起初，鱼 $1,2,3,4$ 的智力分别为 $0,0,0,0$。 - 接下来，JOI 君将一块 $B$ 型食物放入水族箱，被鱼 $3$ 吃掉。结果，鱼 $1,2,3,4$ 的智力分别变为 $0,0,1,1$。 - 然后，JOI 君将一块 $A$ 型食物放入水族箱，被鱼 $1$ 吃掉。结果，鱼 $1,2,3,4$ 的智力分别变为 $2,0,1,1$。 - 最后，JOI 君将一块 $B$ 型食物放入水族箱，被鱼 $1$ 吃掉。结果，鱼 $1,2,3,4$ 的智力分别变为 $3,1,2,2$。 - 由于不放入任何 $A$ 型食物就无法达到所有鱼 $1,2,3$ 的精确理想智力值的状态，输出 $1$。 这个样例满足子任务 $1$ 和 $5$ 的约束条件。 ### 约束条件 - $ 1 \leq N \leq 300,000 $。 - $ 1 \leq Q \leq 300,000 $。 - $ 1 \leq D \leq 10^{12} $。 - $ 0 \leq C_i \leq 10^{12} $（$ 1 \leq i \leq N $）。 - $ 1 \leq L_j \leq R_j \leq N $（$ 1 \leq j \leq Q $）。 - 给定值均为整数。 ### 子任务 - （9 分）$ N \leq 3,000 $，$ Q \leq 3,000 $。 - （7 分）$ C_i \leq 1 $（$ 1 \leq i \leq N $）。 - （28 分）$ D = 1 $。 - （20 分）$ C_i \geq C_{i+1} $（$ 1 \leq i \leq N - 1 $）。 - （36 分）无额外约束。