AT_abc467_g [ABC467G] Many Sweets Problem

有一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\dots,A_N)$。请你处理以下操作 $Q$ 次。 - `c x l r k` ：将 $A_c$ 的值更新为 $x$。然后，解决如下子问题并输出答案。 > 有 $r-l+1$ 颗糖果。第 $i$ 颗糖果的美味度为 $A_{l+i-1}$。 > 你决定吃若干糖果，直到所吃的糖果美味度总和达到 $k$ 或以上为止。 > 如果你可以任意选择吃哪些糖果，最少需要吃多少颗糖果才能让美味度总和达到 $k$？请输出答案。 > 如果无论如何选择都不能让糖果美味度总和达到 $k$，则输出 $-1$。

输入按以下格式由标准输入给出： > $N$ $Q$ $A_1$ $A_2$ $\dots$ $A_N$ $\mathrm{query}_1$ $\mathrm{query}_2$ $\vdots$ $\mathrm{query}_Q$ 每个查询 $\mathrm{query}_q$ 格式如下： > $c$ $x$ $l$ $r$ $k$

输出共 $Q$ 行。你需要输出每个查询的答案，第 $q$ 行对应第 $q$ 次查询的答案。

### 样例解释 1 解释第一个查询。 首先，将 $A_1$ 更新为 $1$。此时 $A=(1,2,4,1,7,3,6)$。现在解决子问题。 在子问题中，有四颗糖果，美味度依次为 $1,7,3,6$。 为了让吃过的糖果美味度和最小的数量达到 $k=9$，最优的吃法是吃第 2 和第 4 颗糖果。因此，子问题答案为 $2$。 ### 数据范围 - $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}$ - 输入中的所有值均为整数。 由 ChatGPT 5 翻译