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

题解

类似于线段树。维护当前比赛以及其前面的比赛的所有可能。以样例为例，初始状态为：

将5从?更新成1时，我们首先更新5的可能数。接着这个更新可能会影响到后续，因此第二步我们更新5的父亲。更新效果如下：

将6更新成?时。我们还是先更新6，接着更新6的父亲，直到根：

将7更新成?时，同理：

于是每次操作最多更新沿途的k个节点。

代码

Java

C++