Playoff Tournament (Codeforces 1535D)
Tags: DP, 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: 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: For each query, print one integer — $$$f(s)$$$.


Sample Inputs:
3
0110?11
6
5 1
6 ?
7 ?
1 ?
5 ?
1 1

Sample Outputs:
1
2
3
3
5
4

Solution (Python):
import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
k = int(input())
a = input()
b = [-1] + [i for i in reversed(a)]
ans = [-1] * len(b) + [1] * 2 ** k
for j in range(len(b) - 1, 0, -1):
    if b[j] == '?':
        ans[j] = ans[2 * j] + ans[2 * j + 1]
    elif b[j] == '0':
        ans[j] = ans[2 * j + 1]
    else:
        ans[j] = ans[2 * j]

def update(i, v):
    j = len(b) - i
    b[j] = v
    while j:
        if b[j] == '?':
            ans[j] = ans[2 * j] + ans[2 * j + 1]
        elif b[j] == '0':
            ans[j] = ans[2 * j + 1]
        else:
            ans[j] = ans[2 * j]
        j //= 2
for _ in range(int(input())):
    (i, v) = input().split()
    i = int(i)
    update(i, v)
    print(ans[1])

Solution (Python):
from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

def main():
    k = int(input())
    s = list('-' + input()[::-1])
    cnt = [0] * len(s)
    for i in range(len(s) // 2, len(s)):
        cnt[i] = 2 if s[i] == '?' else 1
    for i in range(len(s) // 2, len(s)):
        i >>= 1
        while i:
            if s[i] == '?':
                cnt[i] = cnt[i * 2] + cnt[i * 2 + 1]
            elif s[i] == '1':
                cnt[i] = cnt[i * 2]
            else:
                cnt[i] = cnt[i * 2 + 1]
            i >>= 1
    q = int(input())
    for _ in range(q):
        (p, c) = input().split()
        p = len(s) - int(p)
        s[p] = c
        if p >= len(s) // 2:
            cnt[p] = 2 if s[p] == '?' else 1
            p >>= 1
        while p:
            if s[p] == '?':
                cnt[p] = cnt[p * 2] + cnt[p * 2 + 1]
            elif s[p] == '1':
                cnt[p] = cnt[p * 2]
            else:
                cnt[p] = cnt[p * 2 + 1]
            p >>= 1
        print(cnt[1])
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
if sys.version_info[0] < 3:
    (sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()

Solution (Python):
import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
k = int(input())
a = input()
b = [-1] + [i for i in reversed(a)]
ans = [-1] * len(b) + [1] * 2 ** k
for j in range(len(b) - 1, 0, -1):
    if b[j] == '?':
        ans[j] = ans[2 * j] + ans[2 * j + 1]
    elif b[j] == '0':
        ans[j] = ans[2 * j + 1]
    else:
        ans[j] = ans[2 * j]

def update(i, v):
    j = len(b) - i
    b[j] = v
    while j:
        if b[j] == '?':
            ans[j] = ans[2 * j] + ans[2 * j + 1]
        elif b[j] == '0':
            ans[j] = ans[2 * j + 1]
        else:
            ans[j] = ans[2 * j]
        j //= 2
for _ in range(int(input())):
    (i, v) = input().split()
    i = int(i)
    update(i, v)
    print(ans[1])