题解

思路推导

把原字符串反转后，每个字符就可以对应到一棵从编号 $1$ 开始的完全二叉树：根结点对应最后进行的决赛，结点 $v$ 的两个子结点为 $2v$ 和 $2v+1$。由于反转改变了左右顺序，字符 0 对应结点 $2v+1$，字符 1 对应结点 $2v$。

令 $dp_v$ 表示结点 $v$ 所代表的比赛区域中，当前仍可能晋级到该结点的队伍数量。超过字符串范围的叶结点各代表一支队伍，其值为 $1$。若当前字符为 0 或 1，只有指定一侧的队伍能够晋级；若为 ?，两侧的所有可能队伍都可以晋级，因此把两侧计数相加。

一次修改只会影响对应比赛以及它到根结点的祖先链，其他子树的计数保持不变。

做法

先反转字符串，自底向上计算所有结点的 $dp$ 值。对于原字符串位置 $p$，其反转后的结点编号为 $2^k-p$。修改该结点的字符后，不断向父结点移动并重新计算，根结点的值就是当前答案。

正确性证明

对任意结点，若字符已经确定，则只有指定子树中的队伍可能赢得该场比赛；若字符为问号，则两个子树中的任意可能胜者都能通过选择相应比赛结果晋级。因此按照上述转移得到的 $dp_v$，恰好等于该结点覆盖范围内可能晋级的队伍数。

从叶层向根结点归纳，初始计算得到的每个 $dp_v$ 都具有这一含义。修改一场比赛后，只有包含这场比赛的祖先比赛可能改变可能胜者集合；重新计算整条祖先链后，所有受影响结点再次满足定义。于是根结点计数始终恰好等于可能成为冠军的队伍数。

复杂度分析

初始化的时间复杂度和空间复杂度均为 $O(2^k)$。每次修改只经过一条高度为 $k$ 的祖先链，时间复杂度为 $O(k)$。