Necromancer
Contest: Kotlin Heroes: Episode 10
Difficulty rating: 3200
Tags: *special

Monocarp is playing a computer game. In this game, his character is a necromancer. He is fighting $$$n$$$ monsters numbered from $$$1$$$ to $$$n$$$. Each monster has two parameters: health and strength.

Monocarp considers $$$q$$$ scenarios of the battle. In each scenario, he chooses some segment $$$[l, r]$$$ of monsters and calculates the number of moves it takes to defeat all these monsters.

Each scenario proceeds as follows. First, Monocarp kills monster $$$l$$$ and revives it as a zombie (this does not count as a move). Then each move the following happens: let $$$i$$$ be the index of the first monster in the segment $$$[l, r]$$$ that is still alive. All zombies attack monster $$$i$$$, reducing its health by their total strength. After that, if monster $$$i$$$ has $$$0$$$ or less health, it dies and Monocarp revives it as a zombie.

When the monster is revived, the zombie's strength is equal to the monster's strength.

Help Monocarp for each scenario to calculate how many moves it will take to kill all the monsters in the segment.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the number of monsters and the number of scenarios, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^4$$$), where $$$a_i$$$ is the number of health points of the $$$i$$$-th monster.

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^4$$$), where $$$b_i$$$ is the strength of the $$$i$$$-th monster.

Then $$$q$$$ lines follow. The $$$j$$$-th of them contains two integers $$$l_j$$$ and $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — the boundaries of the $$$j$$$-th scenario.

Output format:
For each scenario, print a single integer — the number of moves it will take to kill all the monsters in the segment.

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Example input:
7 5
4 5 9 9 4 2 4
1 3 3 1 2 3 3
3 5
1 4
6 6
1 7
2 6

Example output:
4
10
0
13
7

Editorial:
In this problem, most people were submitting solutions working in $$$O((n+q) \sqrt{A} \log n)$$$, where $$$A$$$ is the maximum monster health value. A good implementation with this complexity might pass, but the model solution has a slightly better complexity: $$$O((n + q) \sqrt{A \log n})$$$.
The main idea is that if we process the first $$$M$$$ monsters for a query naively, then the total strength of zombies becomes at least $$$M$$$, so for every remaining monster, we will use at most $$$\frac{A}{M}$$$ turns.
For every monster $$$i$$$ and every value $$$j$$$ from $$$1$$$ to $$$\frac{A}{M}$$$ we find the minimum left border $$$l$$$ such that, if we consider a query with left border $$$l$$$, we need at least $$$j$$$ operations to kill the monster. It means that the total strength of all monsters from $$$l$$$ to $$$i-1$$$ is less than $$$\lceil \frac{a_i}{j-1} \rceil$$$ (this is the minimum total strength that allows killing the $$$i$$$-th monster in less than $$$j$$$ turns). Using prefix sums, we can find every such border in $$$O(\log n)$$$: let $$$s_i$$$ be the total strength of the first $$$i$$$ monsters. Then, if we consider monsters in $$$0$$$-indexation, we need the minimum $$$l$$$ such that $$$\lceil \frac{a_i}{j-1} \rceil > s_i - s_l$$$. In other words, we need the minimum $$$l$$$ such that $$$s_l > s_i - \lceil \frac{a_i}{j-1} \rceil$$$, and we can use binary search to find it. Let's remember that in this left border $$$l$$$ the number of turns required to kill the $$$i$$$-th monster increases by $$$1$$$.
Then, we use a sweep line approach. Sort all queries according to their left borders, and maintain a data structure that allows adding $$$+1$$$ to a single element and querying the sum on a segment (Fenwick tree, for example). In this structure, for every monster, we store the number of turns required to kill it, considering the current left border. When the left border gets moved from $$$l-1$$$ to $$$l$$$, we add $$$1$$$ to every monster, for which the number of turns increases (it might increase more than by $$$1$$$ for some monsters, but we can handle it because we precalculated the left border for every monster and every number of turns required to kill it).
When we process a query with left border $$$l$$$, our Fenwick tree stores the values of $$$\min(\frac{A}{M}, cnt_{i,l})$$$ for the monsters, where $$$cnt_{i,l}$$$ is the number of turns to kill the $$$i$$$-th monster when we start from the left border $$$l$$$. Process the first $$$M$$$ monsters in the query in $$$O(M)$$$, so our Fenwick tree stores the "actual" values for all remaining monsters, and use a range sum query to process the remaining monsters in $$$O(\log n)$$$.
We get $$$O(n \frac{A}{M} \log n)$$$ for preprocessing and $$$O(M + \log n)$$$ for each query. If we choose $$$M$$$ close to $$$\sqrt{A \log n}$$$, the solution complexity becomes $$$O((n + q) \sqrt{A \log n})$$$.