{"problem":{"name":"[JOIST 2024] 鱼 3 / Fish 3","description":{"content":"JOI 君在一个大水缸中饲养着 $ N $ 条鱼，每条鱼的编号从 $ 1 $ 到 $ N $。 JOI 君有两种类型的鱼食，$ A $ 和 $ B $，两种都有足够的数量。当往水族箱中添加一块食物时，恰好有一条鱼吃掉它（任何鱼都可以吃掉它），并且根据食物的类型以及吃掉它的鱼的情况，鱼的智力变化如下： - 当第 $ k $ 条鱼（$ 1 \\leq k \\leq N $）吃掉一块 $ A $ 型食","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10430"},"statements":[{"statement_type":"Markdown","content":"JOI 君在一个大水缸中饲养着 $ N $ 条鱼，每条鱼的编号从 $ 1 $ 到 $ N $。\n\nJOI 君有两种类型的鱼食，$ A $ 和 $ B $，两种都有足够的数量。当往水族箱中添加一块食物时，恰好有一条鱼吃掉它（任何鱼都可以吃掉它），并且根据食物的类型以及吃掉它的鱼的情况，鱼的智力变化如下：\n\n- 当第 $ k $ 条鱼（$ 1 \\leq k \\leq N $）吃掉一块 $ A $ 型食物时，第 $ k $ 条鱼的智力恰好增加 $ D $。\n- 当第 $ k $ 条鱼（$ 1 \\leq k \\leq N $）吃掉一块 $ B $ 型食物时，编号大于等于 $ k $ 的所有鱼的智力都恰好增加 $ 1 $。\n\n目前，所有鱼的智力都为 $ 0 $。JOI 君希望使第 $ i $ 条鱼（$ 1 \\leq i \\leq N $）的智力等于其理想智力 $ C_i $，但这并不总是可能的。\n\n因此，他考虑了 $ Q $ 个问题。第 $ j $ 个问题（$ 1 \\leq j \\leq Q $）如下：\n\n- 从所有鱼的智力都为 0 的状态开始，通过重复将食物放入水族箱零次或多次的动作，是否可能达到所有鱼 $ L_j , L_j + 1 ,..., R_j $ 都拥有其精确的理想智力值的状态？此外，如果可能，需要放入水族箱的 A 型食物的最小数量是多少？\n\n编写一个程序，给定有关 JOI 君的鱼的信息以及有关问题的信息，回答他的问题。\n\n## Input\n\n从标准输入读取以下数据：\n\n- $ N,D $\n- $ C_1,C_2,...,C_N $\n- $ Q $\n- $ L_1,R_1 $\n- $ L_2,R_2 $\n- ...\n- $ L_Q,R_Q $\n\n## Output\n\n输出共 $Q$ 行。在第 $j$ 行（$ 1 \\leq j \\leq Q $）中，如果可以达到所有鱼 $ L_j $，$ L_j + 1 $，...，$ R_j $ 拥有其精确的理想智力值的状态，则输出需要放入水族箱的 $A$ 型食物的最小数量。否则，输出 $-1$。\n\n[samples]\n\n## Note\n\n#### 样例解释 1\n\n例如，在以下情况下，所有鱼 $1,2,3$ 最终都达到了其精确的理想智力值，且放入水族箱的 $A$ 型食物的数量为 $1$。\n\n- 起初，鱼 $1,2,3,4$ 的智力分别为 $0,0,0,0$。\n- 接下来，JOI 君将一块 $B$ 型食物放入水族箱，被鱼 $3$ 吃掉。结果，鱼 $1,2,3,4$ 的智力分别变为 $0,0,1,1$。\n- 然后，JOI 君将一块 $A$ 型食物放入水族箱，被鱼 $1$ 吃掉。结果，鱼 $1,2,3,4$ 的智力分别变为 $2,0,1,1$。\n- 最后，JOI 君将一块 $B$ 型食物放入水族箱，被鱼 $1$ 吃掉。结果，鱼 $1,2,3,4$ 的智力分别变为 $3,1,2,2$。\n- 由于不放入任何 $A$ 型食物就无法达到所有鱼 $1,2,3$ 的精确理想智力值的状态，输出 $1$。\n\n这个样例满足子任务 $1$ 和 $5$ 的约束条件。\n\n### 约束条件\n\n- $ 1 \\leq N \\leq 300,000 $。\n- $ 1 \\leq Q \\leq 300,000 $。\n- $ 1 \\leq D \\leq 10^{12} $。\n- $ 0 \\leq C_i \\leq 10^{12} $（$ 1 \\leq i \\leq N $）。\n- $ 1 \\leq L_j \\leq R_j \\leq N $（$ 1 \\leq j \\leq Q $）。\n- 给定值均为整数。\n\n### 子任务\n\n- （9 分）$ N \\leq 3,000 $，$ Q \\leq 3,000 $。\n- （7 分）$ C_i \\leq 1 $（$ 1 \\leq i \\leq N $）。\n- （28 分）$ D = 1 $。\n- （20 分）$ C_i \\geq C_{i+1} $（$ 1 \\leq i \\leq N - 1 $）。\n- （36 分）无额外约束。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10430","tags":["2024","JOISC/JOIST（日本）"],"sample_group":[["4 2\n3 1 2 1\n1\n1 3","1"]],"created_at":"2026-03-03 11:09:25"}}