Problem link: 1997E - Level Up

Code (with comments): 273796200

**Hint 1**

The player's level increases slower if we increment $$$k$$$.

**Proof**

Restate the above sentence in a more formal way: Suppose player A and B encounters the same monsters but have different $$$k$$$ ($$$k_A < k_B$$$), then for every level $$$l > 1$$$, player A reaches level $$$l$$$ earlier than B.

We prove it by induction on $$$l$$$.

Case $$$l = 2$$$ is straightforward. A will reach level $$$2$$$ after $$$k_A$$$ monsters, while for B it's $$$k_B$$$ monsters.

If A reaches level $$$l$$$ earlier than B, then when $$$B$$$ reaches level $$$l$$$, A may:

- Already reached level $$$l + 1$$$ or higher;
- Remain at level $$$l$$$. Notice that when B fights a monster, A can fight it too (because their level is same). So after B fights $$$k_A$$$ monsters, he is still level $$$l$$$ while A has upgraded to $$$l + 1$$$.

In both cases, A reaches level $$$l + 1$$$ earlier than B. QED.

**Hint 2**

Therefore, for every monster, there exists a threshold $$$t$$$. If $$$k \ge t$$$, it fights; if $$$k < t$$$, it flees.

After knowing $$$t$$$, it's straightforward to answer the queries.

**Hint 3**

$$$t$$$ only depends on the monster itself and previous monsters. So we can calculate $$$t$$$ one by one.

**Hint 4**

We can find $$$t$$$ using binary search. But we still need a data structure to efficiently find out how many monsters will flee giving a certain $$$k$$$.

**Solution**

Read hints.

We need a data structure that supports:

- Add an element
- Find the number of elements that $$$\leq x$$$

Either a balanced tree or a BIT indexed by element value will do. In both cases, each query is $$$O(\log n)$$$. We need $$$O(\log n)$$$ queries to binary search $$$t$$$ for one monster. The total complexity is $$$O(n \log^2 n)$$$.

However, by using some clever tricks, we can traverse the data structure once and perform binary search simultaneously. This trick eliminates a $$$\log$$$, making the whole algorithm $$$O(n \log n)$$$.

Details can be found in my code.

can you list some more problems which use this idea?

Thanks.

It is the same idea as walking on a segment tree. See also max_right and min_left in atcoder library.