D. Playoff Tournament - 线段树 -建模

Problem - D - Codeforces

D. Playoff Tournament

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

2k2k teams participate in a playoff tournament. The tournament consists of 2k−12k−1 games. They are held as follows: first of all, the teams are split into pairs: team 11 plays against team 22, team 33 plays against team 44 (exactly in this order), and so on (so, 2k−12k−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 2k−12k−1 teams remain. If only one team remains, it is declared the champion; otherwise, 2k−22k−2 games are played: in the first one of them, the winner of the game "11 vs 22" plays against the winner of the game "33 vs 44", then the winner of the game "55 vs 66" plays against the winner of the game "77 vs 88", and so on. This process repeats until only one team remains.

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

Let the string ss consisting of 2k−12k−1 characters describe the results of the games in chronological order as follows:

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

Let f(s)f(s) be the number of possible winners of the tournament described by the string ss. A team ii 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 ii is the champion.

You are given the initial state of the string ss. You have to process qq queries of the following form:

• pp cc — replace spsp with character cc, and print f(s)f(s) as the result of the query.

Input

The first line contains one integer kk (1≤k≤181≤k≤18).

The second line contains a string consisting of 2k−12k−1 characters — the initial state of the string ss. Each character is either ?, 0, or 1.

The third line contains one integer qq (1≤q≤2⋅1051≤q≤2⋅105) — the number of queries.

Then qq lines follow, the ii-th line contains an integer pp and a character cc (1≤p≤2k−11≤p≤2k−1; cc is either ?, 0, or 1), describing the ii-th query.

Output

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

Example

input

Copy

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

output

Copy

1
2
3
3
5
4

=========================================================================

对全部选手做一个线段树，长度为1的区间代表个人。长度大于等于2的区间，恰好有2^k -1个，对应了2^k -1次比赛， 重新编号比赛， 本题中 ，一共有7场比赛，把第i场变成n-i 场，其中n=(2^k)，那么就可以发现， 第七场之余 第五场，第六场的关系，是新编号下 第一场之于 第二场，第三场的关系，也就是 线段树的左右子树关系。

继续考虑 01?对结果的影响， 首先值得关注的一个性质是，我们构造的这个线段树，其左儿子的值一定大于右儿子，如果当前s值对应为 0，那么选择右儿子，1 选择左儿子， ?就选择两者之和即可。

然后是单点修改操作，值得注意的是，我们这个单点修改的这个点，并不是具体的线段树最基础的叶子节点(具体的某个人),而是每场比赛，也就是线段树每个区间的编号，但是传统的自上而下查询的方法并不能帮我们定位到某个具体的区间编号，所以考虑自下而上的更新，获取比赛编号，每次除以2就获得了父亲节点，这样更新时log级别的，方便快捷。

# include<bits/stdc++.h>using namespace std;
typedef long long int ll;
string s;
int id[(1<<19)];
int ans[(1<<19)*4+10];void build(int root,int l,int r)
{if(l==r){ans[root]=1;return ;}int mid=(l+r)>>1;int mproot=id[root];build(root<<1,l,mid);build(root<<1|1,mid+1,r);if(s[mproot]=='?')ans[root]=ans[root<<1]+ans[root<<1|1];else if(s[mproot]=='1')ans[root]=ans[root<<1];elseans[root]=ans[root<<1|1];// cout<<root<<" "<<ans[root]<<endl;
}void change(int root)
{while(root){int mproot=id[root];if(s[mproot]=='?')ans[root]=ans[root<<1]+ans[root<<1|1];else if(s[mproot]=='1')ans[root]=ans[root<<1];elseans[root]=ans[root<<1|1];root>>=1;}}
int main ()
{int n;cin>>n;n=(1<<n);cin>>s;s=" "+s;for(int i=1; i<n; i++){id[i]=n-i;}//左子树更大build(1,1,n);int t;cin>>t;while(t--){int pos;char ch;cin>>pos>>ch;s[pos]=ch;change(id[pos]);cout<<ans[1]<<endl;}return 0;
}