CF1439C.Greedy Shopping

You are given an array $a_1, a_2, \ldots, a_n$ of integers. This array is non-increasing.

Let's consider a line with $n$ shops. The shops are numbered with integers from $1$ to $n$ from left to right. The cost of a meal in the $i$-th shop is equal to $a_i$.

You should process $q$ queries of two types:

• 1 x y: for each shop $1 \leq i \leq x$ set $a_{i} = max(a_{i}, y)$.
• 2 x y: let's consider a hungry man with $y$ money. He visits the shops from $x$-th shop to $n$-th and if he can buy a meal in the current shop he buys one item of it. Find how many meals he will purchase. The man can buy a meal in the shop $i$ if he has at least $a_i$ money, and after it his money decreases by $a_i$.

给你一个整数数组 $a_1, a_2, \ldots, a_n$，该数组是非递增的。

考虑一条直线上有 $n$ 家商店，商店从左到右依次编号为 $1$ 到 $n$。第 $i$ 家商店中一份餐食的价格为 $a_i$。

你需要处理 $q$ 个查询，查询分为两种类型：

• 1 x y：对每个满足 $1 \leq i \leq x$ 的商店 $i$，执行 $a_{i} = \max(a_{i}, y)$。
• 2 x y：假设一位饥饿的人拥有 $y$ 元钱。他从第 $x$ 家商店开始，依次访问第 $x$、$x+1$、…、$n$ 家商店；若他在当前商店有足够的钱购买一份餐食，则他会购买一份。求他总共会购买多少份餐食。该人能在第 $i$ 家商店购买餐食，当且仅当他当前拥有的钱数不少于 $a_i$；购买后，他的钱数减少 $a_i$。

The first line contains two integers $n$, $q$ ($1 \leq n, q \leq 2 \cdot 10^5$).

The second line contains $n$ integers $a_{1},a_{2}, \ldots, a_{n}$ $(1 \leq a_{i} \leq 10^9)$ — the costs of the meals. It is guaranteed, that $a_1 \geq a_2 \geq \ldots \geq a_n$.

Each of the next $q$ lines contains three integers $t$, $x$, $y$ ($1 \leq t \leq 2$, $1\leq x \leq n$, $1 \leq y \leq 10^9$), each describing the next query.

It is guaranteed that there exists at least one query of type $2$.

第一行包含两个整数 $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$ 的查询。

For each query of type $2$ output the answer on the new line.

对于每个类型为 $2$ 的查询，在新行中输出答案。

In the first query a hungry man will buy meals in all shops from $3$ to $10$.

In the second query a hungry man will buy meals in shops $4$, $9$, and $10$.

After the third query the array $a_1, a_2, \ldots, a_n$ of costs won't change and will be ${10, 10, 10, 6, 6, 5, 5, 5, 3, 1}$.

In the fourth query a hungry man will buy meals in shops $2$, $3$, $4$, $5$, $9$, and $10$.

After the fifth query the array $a$ of costs will be ${10, 10, 10, 7, 6, 5, 5, 5, 3, 1}$.

In the sixth query a hungry man will buy meals in shops $2$ and $4$.

在第一次查询中，一个饥饿的人将在第 $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$ 家商店购买餐食。