CF1535D Playoff Tournament

有 $2^k$ 支队伍参加一场淘汰赛。比赛共进行 $2^k - 1$ 场，具体安排如下：首先，所有队伍两两分组：第 $1$ 队对阵第 $2$ 队，第 $3$ 队对阵第 $4$ 队（顺序严格按照编号），以此类推（本轮共进行 $2^{k-1}$ 场比赛）。每场比赛的败者被淘汰，每场比赛必有一队被淘汰（没有平局）。之后，剩下 $2^{k-1}$ 支队伍。如果只剩下一支队伍，则该队成为冠军；否则，继续进行 $2^{k-2}$ 场比赛：在这些比赛中，第一场由“第 $1$ 队对第 $2$ 队”的胜者对阵“第 $3$ 队对第 $4$ 队”的胜者，第二场由“第 $5$ 队对第 $6$ 队”的胜者对阵“第 $7$ 队对第 $8$ 队”的胜者，依此类推。如此循环，直到只剩下一支队伍。 例如，下图描述了 $k=3$ 时比赛的时间顺序：  用一个长度为 $2^k - 1$ 的字符串 $s$ 描述比赛结果，顺序与比赛进行顺序一致： - 如果 $s_i$ 为 $0$，则第 $i$ 场比赛中编号较小的队伍获胜； - 如果 $s_i$ 为 $1$，则第 $i$ 场比赛中编号较大的队伍获胜； - 如果 $s_i$ 为 $?$，则第 $i$ 场比赛结果未知（任意一队都可能获胜）。 定义 $f(s)$ 表示在字符串 $s$ 描述的比赛中，可能成为冠军的队伍数。如果存在一种将所有 $?$ 替换为 $0$ 或 $1$ 的方式，使得第 $i$ 队成为冠军，则第 $i$ 队是可能的冠军。 现在给定初始的字符串 $s$，你需要处理 $q$ 个操作，每个操作如下： - $p$ $c$ —— 将 $s_p$ 替换为字符 $c$，并输出当前 $f(s)$ 的值。

第一行包含一个整数 $k$（$1 \le k \le 18$）。 第二行包含一个长度为 $2^k - 1$ 的字符串，表示初始的 $s$。每个字符为 $?$、$0$ 或 $1$。 第三行包含一个整数 $q$（$1 \le q \le 2 \times 10^5$），表示操作数。 接下来 $q$ 行，每行包含一个整数 $p$ 和一个字符 $c$（$1 \le p \le 2^k - 1$，$c$ 为 $?$、$0$ 或 $1$），表示一次操作。

对于每个操作，输出一个整数，表示当前 $f(s)$ 的值。

由 ChatGPT 4.1 翻译