Each query can be implemented to run in $O(\log n)$ time by lazily propagating appropriate operators on the binary search tree.
The lazy propagation technique *1, is that it is possible to perform range update on a BST as long as such update operations can be composed in $O(1)$ time (forms a monoid).
Let $x_i$ and $m_i$ be the current and the best ranks of the player $i$. Then, let $y_i := x_i - m_i$ be the difference between current and best ranks. We implicitly maintain $x_i$ and $y_i$ on a binary search tree ordered by the score (ties broken arbitrary). A score change can be represented by first removing a player from the BST and then re-inserting the player. Ranks change when:
- When inserting a player, we must down-rank all players $j$ with score less than the inserted player: $x_j \leftarrow x_j + 1$ and $y_j \leftarrow y_j + 1$.
- When removing a player, we must up-rank all players $j$ with score less than the removed player: $x_j \leftarrow x_j - 1$ and $y_j \leftarrow \max(y_j - 1, 0)$.
The operators on $y$ can be represented as a function of the form represented by two numbers $(a, b) \in \mathbb{Z} \times \mathbb{Z} \cup \{-\infty\}$:
$$
f(X) = \max(X + a, b)
$$
and two such functions $f, g$ can be composed:
$$
\begin{align}
(f \circ g)(X) &= \max(\max(X + a_1, b_1) + a_2, b_2) \\
&= \max(\max(X + a_1 + a_2, b_1 + a_2), b_2) \\
&= \max(X + (a_1 + a_2), \max(b_1 + a_2, b_2))
\end{align}
$$
while still being represented by two numbers. That is, the composition is closed and forms a monoid with the identity $(0, -\infty)$. Independently, update on $x$ (range addition) can be represented by just one number.
To summarize, we can implement the required range update operations by storing three additional numbers on each node of the BST. Therefore, it takes $O(\log n)$ time to insert/delete/query a player.
- *1 I don't know a proper reference, but there are many tutorials on the web as a popular competitive programming technique. It is usually written for segment trees (statically allocated full BST) but can adopted to any BST. Rotation/other tree change should trigger a "push" of update operator.
