E - Quiz Competition: Qualifiers

思路

回答的性质：

• 正确答案串 $T$ 始终不变
• 只有两个选项

所以我们不妨把答案看成一个 01 串：记答对为 1，答错为 0。

我们再看题目要求：

• If the number of qualifiers plus the number of undetermined participants who answered the $k$-th question correctly is at most M, then all undetermined participants who answered the $k$-th question correctly become qualifiers.
• Otherwise, all undetermined participants who answered the $k$-th question incorrectly become non-qualifiers.

显然，这就是 01 串字典序从大到小排序：在第一个不同的数位，1 比 0 优先。

但是，我们并不能完全地说这就是取前 $M$ 大的 01 串，至少：

• 当存在多个一模一样的回答串 $S$ 使得一些在前 $M$ 大、另一些不在时，这些串都不能晋级
• 一次也没有答对的串，按原流程永远不会被确定为晋级，但它可能在前 $M$ 大

于是我们就知道怎么判断一个串是否晋级了：

形式化地说，定义

则

把所有 01 串插入二叉字典树，高位在前，1 为右子、0 为左子。原过程等价于从根出发走一条路径 $P$：

• 设在节点 $u$，其子树内有 $c$ 个待定选手，右子（1）有 $c_1$ 个，左子（0）有 $c_0$ 个。
• 若已晋级人数 $+c_1 \le M$：右子树全部晋级，走向左子（0）。
• 否则：左子树全部淘汰，走向右子（1）。

走完 $K$ 步得到串 $P_K$。于是：

1. $x>P_K \Rightarrow$ 晋级：在首个不同位 $x$ 为 1、$P_K$ 为 0，该步选择了走向 0，右子树（含 $x$）已被整体晋级。
2. $x=P_K \Rightarrow$ 淘汰：它们是最后剩余的待定者。
3. $x<P_K \Rightarrow$ 淘汰：在某次「走向 1」时作为左子树被淘汰。

所以晋级集合恰好是 $\{x|x>P_K\}$。下面把它化为只依赖 $x$ 的条件。

• 充分性：$x>P_K$，在首个不同位 $x=1$，故 $x$ 至少答对一题。所有 $\ge x$ 的串都 $>P_K$，从而都在晋级集合内，故 $|H(x)|\le M$。

• 必要性：反设 $x\le P_K$。

  1. 若 $x=P_K$：$x$ 答对至少一题说明 $P_K$ 含 1，即某一步选择了「走向 1」（当时 已晋级 $+c_1>M$）。设该步待定集合大小为 $c$，则 已晋级 $+c>\,$已晋级 $+c_1>M$；而 $H(P_K)\supseteq$ 已晋级 $\cup$ 待定集合，故 $|H(P_K)|>M$，矛盾。
  2. 若 $x<P_K$：在首个不同位 $x=0$、$P_K=1$，即该步「走向 1」，有 已晋级 $+c_1>M$。所有 $\ge x$ 的串包含当时的右子树 $c_1$ 个与已晋级者，故 $|H(x)|\ge$ 已晋级 $+c_1>M$，矛盾。

因此 $x>P_K$，即晋级。结论成立。

代码

字典树初始化时最多要插入 $N * K \leq 3*10^4*200$ 个节点 修改时最多又要插入 $Q * K \leq 5*10^4*200$ 个节点,所以要注意字典树数组空间

// E - Quiz Competition: Qualifiers
#include <iostream>
using namespace std;

const int N = 3e4 + 1023;
int n, m, k, son[2 * N * 200][2], idx, cnt[2 * N * 200], q, num[N];
string t, s[N];

void insert(string s) {
    int p = 0;
    for (int i = 0; i < k; i++) {
        int v = s[i] == t[i];
        if (!son[p][v]) son[p][v] = ++idx;
        p = son[p][v];
        cnt[p]++;
    }
}

void remove(string s) {
    int p = 0;
    for (int i = 0; i < k; i++) {
        int v = s[i] == t[i];
        p = son[p][v];
        cnt[p]--;
    }
}

int query(string s) {
    int p = 0, res = 0;
    for (int i = 0; i < k; i++) {
        int v = s[i] == t[i];
        if (v == 0) res += cnt[son[p][1]];
        p = son[p][v];
    }
    res += cnt[p];
    return res;
}

int main() {
    cin >> n >> m >> k >> t;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        insert(s[i]);
        for (int j = 0; j < k; j++)
            num[i] += s[i][j] == t[j];
    }
    cin >> q;
    for (int i, j; q--;) {
        cin >> i >> j;
        remove(s[i]);
        s[i][j - 1] = s[i][j - 1] == 'o' ? 'x' : 'o';
        if (s[i][j - 1] == t[j - 1]) num[i]++;
        else num[i]--;
        insert(s[i]);
        if (num[i] > 0 && query(s[i]) <= m) puts("Yes");
        else puts("No");
    }
    return 0;
}