题意：有\(2^k\)个队伍进行\(2^k-1\)场比赛,1和2比,3和4比,...,每两两决出胜者进行下一轮,现在给你一长度为\(2^k-1\)的字符串,每个位置代表按顺序的比赛结果,\(0\)表示下标小的队伍胜,\(1\)表示下标大的队伍胜,?表示未知,有\(q\)个询问,每次修改字符串的一个字符,问最后有多少可能的冠军。

题解：线段树,每个结点维护其所有子结点的可能冠军数,根据线段树性质,反转一下(push_up时要反过来),然后维护即可,询问的时候直接向上维护,更方便一点。

代码:

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
 
int n;
string s;
int num;
 
struct misaka{
	int cnt;
}tr[N<<4];
 
void push_up(int u){
	if(s[u]=='0'){
		tr[u].cnt=tr[u<<1|1].cnt;
	}
	if(s[u]=='1'){
		tr[u].cnt=tr[u<<1].cnt;
	}
	if(s[u]=='?'){
		tr[u].cnt=tr[u<<1].cnt+tr[u<<1|1].cnt;
	}
}
 
void build(int u,int l,int r){
	if(l==r){
		tr[u].cnt=1;
		return;
	}
	int mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	push_up(u);
	//cout<<u<<' '<<tr[u].cnt<<'\n';
}
 
 
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	cin>>s;
	reverse(s.begin(),s.end());
	s=" "+s;
	int q;
	cin>>q;
	num=1<<n;
 
	build(1,1,num);
 
	while(q--){
		int p;
		char c;
		cin>>p;
		cin>>c;
		p=num-p;
		s[p]=c;
		for(int i=p;i;i>>=1){
			if(s[i]=='1') tr[i].cnt=tr[i<<1].cnt;
			else if(s[i]=='0') tr[i].cnt=tr[i<<1|1].cnt;
			else tr[i].cnt=tr[i<<1].cnt+tr[i<<1|1].cnt;
		}
		cout<<tr[1].cnt<<'\n';
	}
 
    return 0;
}