Greedy Shopping
Contest: Codeforces Round 684 (Div. 1)
Difficulty rating: 2600
Tags: binary search, data structures, divide and conquer, greedy, implementation

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$$$.

Input format:
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$$$.

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

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
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

Example output:
8
3
6
2

Editorial:
We can prove that the hungry man will eat at most $$$log_2(maxY)$$$ continiuous subsegments, where $$$maxY$$$ is the maximum amount of money possible. Why is that so? Suppose the hungry man buys a meal from the $$$i$$$ th shop but can't buy a meal from the $$$(i + 1)$$$th one after that. Then, the money the hungry man had before buying the $$$i$$$th food is at most twice the money he has after buying the $$$i$$$th food because $$$a_i > a_{i+1}$$$. So every time he breaks the subsegment of shops, his money is cut in at least half, so he will eat atmost $$$log_2(maxY)$$$ continuous subsegments.
Now we need a data structure with the following queries: range_max and range_sum. Since our array is non-increasing, a segment tree will suffice. The first type of query is just a range_max query. For the second type of query you can find the first element that is equal to or smaller than the hungry man's money and after that find the segment that he will eat, in which we can use a binary-search on the tree to find these both. After that we can repeat this action untill we reach the end of the array, or until his money runs out.
Time complexity: $$$O((n + q)log(maxY)log(n))$$$