CF1439C Greedy Shopping

给定一个整数数组 $a_1, a_2, \ldots, a_n$，该数组是非递增的。 现在有一条街道，上面有 $n$ 家商店，商店从左到右编号为 $1$ 到 $n$。第 $i$ 家商店的一顿饭的价格为 $a_i$。 你需要处理 $q$ 个两种类型的操作： - 1 x y：对于每个 $1 \leq i \leq x$，将 $a_i$ 赋值为 $\max(a_i, y)$。 - 2 x y：有一个手里有 $y$ 元钱的饥饿的人，他会从第 $x$ 家商店开始，依次访问到第 $n$ 家商店。如果他有足够的钱购买当前商店的饭（即手里的钱不少于 $a_i$），他就会买一份，并且钱减少 $a_i$。请你计算他能买到多少份饭。

第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 2 \times 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示每家商店的饭的价格。保证 $a_1 \geq a_2 \geq \ldots \geq a_n$。 接下来的 $q$ 行，每行包含三个整数 $t$、$x$、$y$（$1 \leq t \leq 2$，$1 \leq x \leq n$，$1 \leq y \leq 10^9$），描述一个操作。 保证至少有一个操作是类型 $2$。

对于每个类型为 $2$ 的操作，输出一行答案。

在第一个询问中，饥饿的人会在第 $3$ 到第 $10$ 家商店都买到饭。 在第二个询问中，饥饿的人会在第 $4$、$9$ 和 $10$ 家商店买到饭。 第三个操作后，价格数组 $a_1, a_2, \ldots, a_n$ 不会发生变化，仍为 $\{10, 10, 10, 6, 6, 5, 5, 5, 3, 1\}$。 在第四个询问中，饥饿的人会在第 $2$、$3$、$4$、$5$、$9$ 和 $10$ 家商店买到饭。 第五个操作后，价格数组 $a$ 变为 $\{10, 10, 10, 7, 6, 5, 5, 5, 3, 1\}$。 在第六个询问中，饥饿的人会在第 $2$ 和第 $4$ 家商店买到饭。 由 ChatGPT 4.1 翻译