Playoff Tournament
Contest: Educational Codeforces Round 110 (Rated for Div. 2)
Difficulty rating: 1800
Tags: data structures, dfs and similar, dp, implementation, trees

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

Input format:
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.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3
0110?11
6
5 1
6 ?
7 ?
1 ?
5 ?
1 1

Example output:
1
2
3
3
5
4

Editorial:
Denote $$$cnt_i$$$ as the number of teams that can be winners in the $$$i$$$-th game. The answer to the problem is $$$cnt_{2^k-1}$$$.
If the $$$i$$$-th game is played between the winners of games $$$x$$$ and $$$y$$$ ($$$x < y$$$), then:
• $$$cnt_i = cnt_x$$$ if $$$s_i = 0$$$;
• $$$cnt_i = cnt_y$$$ if $$$s_i = 1$$$;
• $$$cnt_i = cnt_x + cnt_y$$$ if $$$s_i = ?$$$.
So we can calculate all values of $$$cnt$$$ for the initial string.
Note that the result of no more than $$$k$$$ other games depends on the result of any game. So, if we change $$$s_p$$$, it will change no more than $$$k$$$ values of $$$cnt$$$, and we can recalculate all of them.
For convenience, you can renumerate the games so that the playoff looks like a segment tree, i. e. the final has the number $$$0$$$, the semifinals have numbers $$$1$$$ and $$$2$$$, etc.