1535D - Playoff Tournament - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
const int N = (1<<18) + 5;
int k, n, q, dp[N], nIdx[N], idx[N];
string s;
void go(int i, int lvl, int x){
  if(lvl == x){
    dp[i] = ((s[nIdx[i]] == '?') ? 2 : 1);
    return;
  }
  go(2*i, lvl+1, x);
  go(2*i + 1, lvl+1, x);
  if(s[nIdx[i]] == '?'){
    dp[i] = dp[2*i] + dp[2*i + 1]; 
  } else if(s[nIdx[i]] == '1'){
    dp[i] = dp[2*i + 1]; 
  } else{
    dp[i] = dp[2*i];
  }
}
void build(string &str){
  int len = size(str);
  int lvl = __builtin_popcount(len) - 1, cur = 0;
  for(int k = lvl; k >= 0; k--){
    for(int j = 0; j < (1<<k); j++){
      idx[cur] = (1<<k)+j;
      nIdx[(1<<k)+j] = cur++;
    }
  }
  go(1, 0, lvl);
}
void update(int pos, int mx){
  if(2*pos > mx){
    if(s[nIdx[pos]] == '?')dp[pos] = 2;
    else dp[pos] = 1;
  }else{ 
    if(s[nIdx[pos]] == '?')
      dp[pos] = dp[pos<<1] + dp[pos<<1|1];
    else if(s[nIdx[pos]] == '1')dp[pos] = dp[pos<<1|1];
    else dp[pos] = dp[pos<<1];
  }
  if(pos/2 > 0)update(pos/2, mx);
}

int main()
{
  cin.tie(0) -> sync_with_stdio(false);
  cin>>n>>s>>q;
  build(s);
  int mx = s.size();
  while(q--){
    int pos; char x;
    cin>>pos>>x;
    char xx = s[--pos];
    s[pos] = x;  update(idx[pos], mx); 
    cout<<dp[1]<<'\n';
  }
}