← 返回题目列表

Codeforces · 1535/D

D. 季后赛

中文机器翻译题面 查看原题

$$$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$$$ 的游戏的时间顺序:

设由 $$$2^k - 1$$$ 个字符组成的字符串 $$$s$$$ 按时间顺序描述游戏结果如下:

- 如果 $$$s_i$$$ 为 0,则指数较低的球队赢得第 $$$i$$$ 场比赛;
- 如果 $$$s_i$$$ 为 1,则索引较大的球队赢得第 $$$i$$$ 场比赛;
- 如果 $$$s_i$$$ 为 ?,则第 $$$i$$$ 场比赛的结果未知(任何球队都可能赢得这场比赛)。

令 $$$f(s)$$$ 为字符串 $$$s$$$ 描述的锦标赛可能获胜者的数量。如果可以替换每个 ?,一支队伍 $$$i$$$ 可能成为锦标赛的获胜者。要么 1 要么 0,这样 $$$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 \cdot 10^5$$$) — 查询数。

接下来是 $$$q$$$ 行,第 $$$i$$$ 行包含一个整数 $$$p$$$ 和一个字符 $$$c$$$ ($$$1 \le p \le 2^k - 1$$$; $$$c$$$ 是 ?、0 或 1),描述第 $$$i$$$ 查询。

输出

对于每个查询,打印一个整数 — $$$f(s)$$$。

示例

输入 #1

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

输出 #1

1
2
3
3
5
4