CF1535D.Playoff Tournament

$2^k$ teams participate in a playoff tournament. The tournament consists of $2^k - 1$ games. They are held as follows: first of all, the teams are split into pairs: team $1$ plays against team $2$, team $3$ plays against team $4$ (exactly in this order), and so on (so, $2^{k-1}$ games are played in that phase). When a team loses a game, it is eliminated, and each game results in elimination of one team (there are no ties). After that, only $2^{k-1}$ teams remain. If only one team remains, it is declared the champion; otherwise, $2^{k-2}$ games are played: in the first one of them, the winner of the game "$1$ vs $2$" plays against the winner of the game "$3$ vs $4$", then the winner of the game "$5$ vs $6$" plays against the winner of the game "$7$ vs $8$", and so on. This process repeats until only one team remains.

For example, this picture describes the chronological order of games with $k = 3$:

Let the string $s$ consisting of $2^k - 1$ characters describe the results of the games in chronological order as follows:

• if $s_i$ is 0, then the team with lower index wins the $i$-th game;
• if $s_i$ is 1, then the team with greater index wins the $i$-th game;
• if $s_i$ is ?, then the result of the $i$-th game is unknown (any team could win this game).

Let $f(s)$ be the number of possible winners of the tournament described by the string $s$. A team $i$ is a possible winner of the tournament if it is possible to replace every ? with either 1 or 0 in such a way that team $i$ is the champion.

You are given the initial state of the string $s$. You have to process $q$ queries of the following form:

• $p$ $c$ — replace $s_p$ with character $c$, and print $f(s)$ as the result of the query.

$2^k$ 支队伍参加一场淘汰赛锦标赛。该锦标赛共进行 $2^k - 1$ 场比赛，赛程安排如下：首先将所有队伍两两分组：第 $1$ 支队伍对阵第 $2$ 支队伍，第 $3$ 支队伍对阵第 $4$ 支队伍（严格按此顺序），依此类推（因此该阶段共进行 $2^{k-1}$ 场比赛）。每场比赛中，失败的队伍被淘汰；每场比赛恰好淘汰一支队伍（无平局）。此后，仅剩 $2^{k-1}$ 支队伍。若只剩一支队伍，则该队被宣布为冠军；否则，再进行 $2^{k-2}$ 场比赛：第一场由“第 $1$ 场 vs 第 $2$ 场”的胜者对阵“第 $3$ 场 vs 第 $4$ 场”的胜者，第二场由“第 $5$ 场 vs 第 $6$ 场”的胜者对阵“第 $7$ 场 vs 第 $8$ 场”的胜者，依此类推。该过程不断重复，直至仅剩一支队伍。

例如，下图描述了当 $k = 3$ 时各场比赛的时间顺序：

设字符串 $s$ 由 $2^k - 1$ 个字符组成，按时间顺序描述各场比赛结果，规则如下：

• 若 $s_i$ 为 0，则第 $i$ 场比赛中索引较小的队伍获胜；
• 若 $s_i$ 为 1，则第 $i$ 场比赛中索引较大的队伍获胜；
• 若 $s_i$ 为 ?，则第 $i$ 场比赛结果未知（任意一支队伍均可获胜）。

定义 $f(s)$ 为字符串 $s$ 所描述锦标赛中可能的冠军数量。称队伍 $i$ 是锦标赛的一个可能冠军，当且仅当可以将每个 ? 替换为 0 或 1，使得队伍 $i$ 最终成为冠军。

给定字符串 $s$ 的初始状态。你需要处理 $q$ 个如下形式的查询：

• p c — 将 $s_p$ 替换为字符 $c$，并输出此次查询后 $f(s)$ 的值。

The first line contains one integer $k$ ($1 \le k \le 18$).

The second line contains a string consisting of $2^k - 1$ characters — the initial state of the string $s$. Each character is either ?, 0, or 1.

The third line contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries.

Then $q$ lines follow, the $i$-th line contains an integer $p$ and a character $c$ ($1 \le p \le 2^k - 1$; $c$ is either ?, 0, or 1), describing the $i$-th query.

第一行包含一个整数 $k$（$1 \le k \le 18$）。

第二行包含一个由 $2^k - 1$ 个字符组成的字符串——字符串 $s$ 的初始状态。每个字符为 ?、0 或 1 中的一个。

第三行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$）——查询次数。

接下来有 $q$ 行，其中第 $i$ 行包含一个整数 $p$ 和一个字符 $c$（$1 \le p \le 2^k - 1$；$c$ 为 ?、0 或 1 中的一个），描述第 $i$ 个查询。

For each query, print one integer — $f(s)$.

对于每个查询，输出一个整数——$f(s)$。