Playoff Tournament

题意翻译

给定整数 $k$，现在有 $2^k$ 支队伍（编号为 $1$ 到 $2^k$）进行共 $2^k-1$ 场比赛，流程如下： 1. 第 $1$ 支与第 $2$ 支进行比赛、第 $3$ 支与第 $4$ 支进行比赛，以此类推，这一阶段总共进行 _队伍数除以二_ 场比赛。这些比赛中必定分出胜负，负方淘汰，胜方继续下一轮的比赛； 2. 重复进行上述步骤，直到只有一支队伍没有被淘汰，这支队伍成为冠军。 （依据原题目描述中的图片来获得更好理解。该图满足 $k=3$。） 给定一个长度为 $2^k-1$ 的、仅包含字符 `0 1 ?` 的字符串 $s$，具体的： - 如果 $s_i=\texttt{"0"}$，表示第 $i$ 次比赛中，编号更小的队伍获胜。 - 如果 $s_i=\texttt{"1"}$，表示第 $i$ 次比赛中，编号更大的队伍获胜。 - 如果 $s_i=\texttt{"?"}$，表示第 $i$ 次比赛中，任意一方都可能获胜。 设 $f(s)$ 表示根据字符串 $s$，所有可能成为冠军的不同的队伍数。 给定查询次数 $q$，每次查询给定整数 $p$ 和字符 $c$，求将 $s$ 的第 $p$ 位修改为 $c$ 后 $f(s)$ 的值。 应注意的是，每次询问之间**并不是互相独立的**，也就是说每一次查询都会影响之后的查询。 $1\leq k\leq18;|s|=2^k-1;1\leq q\leq2\times10^5;1\leq p\leq|s|;$ $s,c$ 仅包含字符 `0 1 ?`。

题目描述

$ 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.

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

3
0110?11
6
5 1
6 ?
7 ?
1 ?
5 ?
1 1

输出样例 #1

1
2
3
3
5
4