Educational Codeforces Round 110 Playoff Tournament Solution (Java/C++)

Solution:

Like segment tree. Maintain all the possibilities of the current game and the earlier game. For sample data, the Initial state:

When update 5th game from "?" to 1, firstly we update the number of possibilities. After that, this change may affect the games after that. So, the second step is updating the father of 5th game. Like this:

When update 6th game to "?". We update 6th game first, then update the fathers of it, until updated root. Like this:

When update the 7th game, same thing:

So, each operation, at most update k games status.

Code:

Java

C++