← 返回题目列表

Codeforces · 1439/C

C. 贪婪购物

中文机器翻译题面 查看原题

给定一个整数数组 $$$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$$$ 钱,他就可以在商店 $$$i$$$ 买一顿饭,之后他的钱就会减少 $$$a_i$$$。

输入

第一行包含两个整数 $$$n$$$、$$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 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$$$ 类型的每个查询,在新行上输出答案。

示例

输入 #1

10 6
10 10 10 6 6 5 5 5 3 1
2 3 50
2 4 10
1 3 10
2 2 36
1 4 7
2 2 17

输出 #1

8
3
6
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$$$ 商店购买食物。