Problem link: 1997E - Прокачка персонажа
Code (with comments): 273796200
The player's level increases slower if we increment $$$k$$$.
Restate the above sentence in a more formal way: Suppose player A and B encounters the same monsters but have different $$$k$$$ ($$$k_A \lt k_B$$$), then for every level $$$l \gt 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.
Therefore, for every monster, there exists a threshold $$$t$$$. If $$$k \ge t$$$, it fights; if $$$k \lt t$$$, it flees.
After knowing $$$t$$$, it's straightforward to answer the queries.
$$$t$$$ only depends on the monster itself and previous monsters. So we can calculate $$$t$$$ one by one.
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$$$.
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.