Playoff Tournament

Created by LXC on Sat Jul 15 14:19:46 2023

https://codeforces.com/problemset/problem/1535/D

ranting: 1800

tag: data structures, dfs and similar, dp, implementation, trees

problem

有$2^k$个队伍，两两对决，败者退出。共计打了$2^k-1$场比赛。

现在给出了$2^k-1$场比赛的情况：当为1时，编号大的队伍胜出；当为0时，编号小的队伍胜出；当为?时胜出队伍不确定。

有q次操作。每次操作会修改某次比赛的结果，现在求每次修改后最后的赢家有多少种可能。

$1\le k\le 18, 1 \le q \le 2\cdot10^5$

solution

我们可以将所有的比赛看作一颗完全二叉树，每次修改一个节点，只会影响祖先节点。

所以一次修改只会影响最多k场比赛的结果。

时间复杂度$O(qk)$

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n, q;
    string s;
    cin >> n >> s >> q;
    reverse(s.begin(), s.end());
    for (auto& i : s) {
        if (i == '1')
            i = '0';
        else if (i == '0')
            i = '1';
    }
    // cout << s << endl;
    int sz = (1 << n) - 1;
    vector<int> v(1 << n + 1, 1);
    for (int i = sz - 1; i >= 0; i--) {
        if (s[i] == '1')
            v[i] = v[2 * i + 2];
        if (s[i] == '0')
            v[i] = v[2 * i + 1];
        if (s[i] == '?')
            v[i] = v[2 * i + 1] + v[2 * i + 2];
    }
    while (q--) {
        int p;
        string c;
        cin >> p >> c;
        p = sz - p;
        if (c[0] != '?')
            c[0] = 1 - (c[0] - '0') + '0';
        s[p] = c[0];
        while (1) {
            if (s[p] == '1')
                v[p] = v[p * 2 + 2];
            if (s[p] == '0')
                v[p] = v[p * 2 + 1];
            if (s[p] == '?')
                v[p] = v[2 * p + 1] + v[2 * p + 2];
            if (p == 0)
                break;
            p = (p - 1) / 2;
        }
        cout << v[0] << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}