Properties of the Problem “Marunomi”

The problem “Marunomi” has the following properties:

• If the maximum final weights of slime \( i \) and slime \( j \) are different, the ratio of their weights is at least 2.
• The number of distinct maximum final weights is \( O(\log (N \max(W))) \).

Solution

Since the number of distinct victory counts for slimes in each prefix is at most \( O(\log (N \max(W))) \), we propose maintaining a set of pairs that represent the minimum and maximum weights of slimes with the same victory count, updating this set as necessary.

First, we use data structures such as a segment tree or binary indexed tree, which support point updates and range sum queries, to keep track of the sum of weights of slimes smaller than the current weight.

Now, consider adding a new slime.

The calculation of the victory count for the newly added slime takes \( O(\log N \log(N \max(W))) \). Similarly, updating slimes with the same victory count can also be performed in \( O(\log N \log (N \max(W))) \). As a result, the entire process can be executed in \( O(\log N \log^2 (N \max(W))) \). Additionally, merging slimes with the same victory count can be done in \( O(\log (N \max(W))) \).

Thus, this problem can be solved in \( O(N \log N \log^2(N \max(W))) \). Furthermore, by leveraging the properties of the problem and reducing the number of accesses to the data structure for point updates and range queries during each update, it is possible to achieve a time complexity of \( O(N \log N \log(N \max(W))) \).