G. Many Sweets Problem

AtCoder Beginner Contest 467

Many Sweets Problem

AtCoder

⌀ 2544

原题

← E→

Many Sweets ProblemAI (CI翻译)

Problem Statement

There is a length- $N$ sequence of positive integers $A=(A_1,A_2,\dots,A_N)$ . Process the following query $Q$ times.

c x l r k : Update the value of $A_c$ to $x$ . Then, solve the following sub-problem and output the answer.

There are $r-l+1$ sweets. The deliciousness of the $i$ -th sweet is $A_{l+i-1}$ . You decide to eat sweets until the total deliciousness of the sweets eaten becomes $k$ or more. What is the minimum possible number of sweets you eat, if you optimally choose which sweets to eat? Output the answer. If the total deliciousness cannot become $k$ or more no matter how you choose the sweets to eat, output $-1$ instead.

Constraints

$1 \leq N \leq 10^5$
$1 \leq Q \leq 10^5$
$1 \leq A_i \leq 10^9$
$1 \leq c \leq N$
$1 \leq x \leq 10^9$
$1 \leq l \leq r \leq N$
$1 \leq k \leq 10^{15}$
All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
A_1 A_2 \dots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query $\mathrm{query}_q$ is given in the following format:

c x l r k

Output

Output $Q$ lines. The $q$ -th line should contain the answer to the $q$ -th query.

{"titleZh":"许多糖果问题","bodyZh":"## 题目描述\n\n有一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\\dots,A_N)$ 。请处理 $Q$ 次以下查询。\n\n- c x l r k：将 $A_c$ 的值更新为 $x$ 。然后解决以下子问题并输出答案。\n\n> 有 $r-l+1$ 颗糖果。第 $i$ 颗糖果的美味度为 $A_{l+i-1}$ 。\n> 你决定不断吃糖果，直到吃下的糖果的美味度总和达到 $k$ 或更高。\n> 如果你能最优地选择要吃的糖果，那么最少需要吃多少颗糖果？请输出这个数。\n> 如果无论如何选择糖果，美味度总和都无法达到 $k$ 或更高，则输出 $-1$ 。\n\n## 约束条件\n\n- $1 \\leq N \\leq 10^5$ \n- $1 \\leq Q \\leq 10^5$ \n- $1 \\leq A_i \\leq 10^9$ \n- $1 \\leq c \\leq N$ \n- $1 \\leq x \\leq 10^9$ \n- $1 \\leq l \\leq r \\leq N$ \n- $1 \\leq k \\leq 10^{15}$ \n- 所有输入值均为整数。\n\n## 输入格式\n\n输入从标准输入给出，格式如下：\n\n\nN Q\nA_1 A_2 \\dots A_N\n\\mathrm{query}_1\n\\mathrm{query}_2\n\\vdots\n\\mathrm{query}_Q\n`\n\n每次查询 $\mathrm{query}_q$ 的格式如下：\n\n`\nc x l r k\n\n\n## 输出格式\n\n输出 $Q$ 行。第 $q$ 行应包含第 $q$ 次查询的答案。"}AI (CI翻译)

样例

Input #1

7 5
8 2 4 1 7 3 6
1 1 4 7 9
5 2 1 3 8
6 4 1 5 9
6 5 3 5 1
7 9 4 6 4

Output #1

We explain the first query. First, update $A_1$ to $1$. Then, $A=(1,2,4,1,7,3,6)$. Now, solve the sub-problem. In the sub-problem, there are four sweets, with deliciousness $1,7,3,6$ in order. To minimize the number of sweets eaten so that the total deliciousness becomes $k=9$ or more, it is optimal to eat the second and fourth sweets. Thus, the answer to the sub-problem is $2$.

Input #2

15 10
993115119 576136368 21553212 219853538 853822501 687675302 281611653 844033520 423210108 339630584 780395612 207907746 285523486 359061085 14767613
6 13801767 1 3 667406485
7 672229269 5 7 855399219
11 2367096 1 10 4016308479
6 5951398 8 8 413598120
6 196639646 5 11 2483790193
14 105322777 6 7 610670157
7 416730828 2 14 1236755516
9 838827476 5 14 4350335977
1 894919681 3 7 1132967029
6 932707551 6 15 1694677398

Output #2

题目信息

题号

abc467_g

所属比赛

AtCoder Beginner Contest 467

时间限制

3 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。