P13276 [NOI2025] 绝对防御

defense.cpp / 4 s / 1024 MiB

小 Q 在与电脑玩一款名为“绝对防御”的回合制卡牌游戏。 小 Q 有一个大小为 $n$ 的牌堆，包含两种牌：攻击牌与防御牌。游戏开始时，小 Q 会从**牌堆顶**抽取 $k \ (1 \leq k \leq n)$ 张牌作为初始手牌，接下来他会与电脑进行若干轮对战。 每轮对战开始时，小 Q 从牌堆顶抽取 $2$ 张牌。特别地，若牌堆只剩余 $1$ 张牌，则小 Q 只抽取 $1$ 张。一轮对战分为两个**回合**： - 第一回合：小 Q 为攻击方，电脑为防御方； - 第二回合：小 Q 为防御方，电脑为攻击方。 在每**回合**中，攻击方**必须**从手牌中选择一张**攻击牌**进行攻击，防御方**必须**从手牌打出一张**防御牌**进行防御。无法按要求出牌者立即判负。 电脑的攻击牌与防御牌都是无限的，即电脑总能打出对应牌。为平衡电脑的实力，小 Q 可以使用一种特殊技能：当小 Q 为**防御方**时，他可以从手牌打出一张**攻击牌**进行防御。该技能每 $3$ 轮**对战**才能使用一次，即在某轮使用技能后，接下来的 $2$ 轮对战中不能使用该技能。 在给定规则下，小 Q 的获胜目标为在电脑猛烈攻击中幸存，即在某轮对战结束后，牌堆被抽空。特别地，若游戏开始时牌堆已被抽空，则小 Q 直接达成获胜目标。小 Q 想知道最小的初始抽牌数 $k$，使得他能达成胜利目标。 小 Q 觉得这个问题过于简单，因此他增加了 $q$ 次修改操作。第 $i \ (1 \leq i \leq q)$ 次修改操作给定一个正整数 $x_i$，改变牌堆顶到牌堆底的第 $x_i$ 张牌的类型，即将攻击牌变为防御牌，将防御牌变为攻击牌。你需要对初始牌堆及每次修改后的牌堆，求出最小的小 Q 初始抽牌数 $k$，使得小 Q 能达成胜利目标。

**本题包含多组测试数据**。 输入的第一行包含两个非负整数 $c,t$，分别表示测试点编号与测试数据组数。$c = 0$ 表示测试点为样例。 接下来依次输入每组测试数据，对于每组测试数据： 第一行包含两个非负整数 $n, q$，分别表示牌堆大小与修改次数。 第二行包含一个长度为 $n$ 的字符串 $s_1 s_2 \ldots s_n$，分别表示从牌堆顶到底的每张牌， 其中 $s_i = 0$ 表示第 $i$ 张牌为攻击牌，$s_i = 1$ 表示第 $i$ 张牌为防御牌。 第 $i + 2 \ (1 \leq i \leq q)$ 行包含一个正整数 $x_i$，表示第 $i$ 次修改的牌为从牌堆顶到牌堆底的第 $x_i$ 张牌。

对于每组测试数据，设初始时的答案为 $k_0$，第 $i$ ($1 \leq i \leq q$) 次修改后的答案为 $k_i$，输出一行 $q+1$ 个正整数 $k_0,k_1,\ldots,k_q$，表示初始时及每次修改后的最小抽牌数，使得小 Q 能达成获胜目标。

#### 【样例 1 解释】 该样例共包含三组测试数据。 对于第一组测试数据： - 初始时，牌堆为 $01010$。若初始抽牌数为 $1$，小 Q 的一种可能的出牌方式为： - 初始时手牌为 $\{0\}$; - 从堆顶抽取两张牌，打出一张攻击牌，一张防御牌，手牌变为 $\{0\}$; - 从堆顶抽取两张牌，打出一张攻击牌，一张防御牌，手牌变为 $\{0\}$，此时牌堆被抽空。 由于初始至少需要抽取一张牌，所以最小初始抽牌数为 $1$，故 $k_0=1$。 - 第一次修改后，牌堆变为 $01000$。若初始抽牌数为 $1$，小 Q 的一种可能的出牌方式为： - 初始时手牌为 $\{0\}$; - 从堆顶抽取两张牌，打出一张攻击牌，一张防御牌，手牌变为 $\{0\}$; - 从堆顶抽取两张牌，打出一张攻击牌，使用特殊技能再次打出一张攻击牌进行防御，手牌变为 $\{0\}$，此时牌堆被抽空。 由于初始至少需要抽取一张牌，所以最小初始抽牌数为 1，故 $k_1=1$。 对于第二组测试数据： 若初始抽牌数为 $3$，小 Q 的一种可能的出牌方式为： - 初始时手牌为 $\{0,0,0\}$; - 从堆顶抽取两张牌，打出一张攻击牌，一张防御牌，手牌变为 $\{0,0,0\}$; - 从堆顶抽取两张牌，打出一张攻击牌，使用特殊技能再次打出一张攻击牌进行防御，手牌变为 $\{0,0,0\}$，此时牌堆被抽空。 可以证明，不存在比 $3$ 更小的初始抽牌数能够抽空牌堆，故答案为 $3$。 对于第三组测试数据： 若初始抽牌数为 $2$，小 Q 的一种可能的出牌方式为： - 初始时手牌为 $\{0,0\}$; - 从堆顶抽取两张牌，打出一张攻击牌，使用特殊技能再次打出一张攻击牌进行防御，手牌变为 $\{0,1\}$; - 从堆顶抽取两张牌，打出一张攻击牌，一张防御牌，手牌变为 $\{0,1\}$; - 从堆顶抽取两张牌，打出一张攻击牌，一张防御牌，手牌变为 $\{0,0\}$，此时牌堆被抽空。 可以证明，不存在比 $2$ 更小的初始抽牌数能够抽空牌堆，故答案为 $2$。 【样例 2】 见选手目录下的 `defense/defense2.in` 与 `defense/defense2.ans`。 该样例满足测试点 2 的约束条件。 【样例 3】 见选手目录下的 `defense/defense3.in` 与 `defense/defense3.ans`。 该样例满足测试点 5 ~ 7 的约束条件。 【样例 4】 见选手目录下的 `defense/defense4.in` 与 `defense/defense4.ans`。 该样例满足测试点 9,10 的约束条件。 【样例 5】 见选手目录下的 `defense/defense5.in` 与 `defense/defense5.ans`。 该样例满足测试点 11 的约束条件。 【样例 6】 见选手目录下的 `defense/defense6.in` 与 `defense/defense6.ans`。 该样例满足测试点 12 ~ 14 的约束条件。 ### 数据范围 设 $N, Q$ 分别为单个测试点内所有测试数据的 $n, q$ 的和。对于所有测试数据，保证： - $1 \leq t \leq 10^5$； - $1 \leq n \leq 2 \times 10^5$，$N \leq 5 \times 10^5$； - $0 \leq q \leq 2 \times 10^5$，$Q \leq 5 \times 10^5$； - 对于所有 $1 \leq i \leq n$，均有 $s_i \in \{ 0, 1 \}$； - 对于所有 $1 \leq i \leq q$，均有 $1 \leq k_i < n$。 ::cute-table{tuack} | 测试点编号 | $n \leq$ | $q \leq$ | $N, Q \leq$ | 特殊性质 | |:------------:|:---------:|:----------:|:-------------:|:----------:| | $1 $ | $20 $ | $20 $ | $60 $ | 无 | | $2 $ | $10^2 $ | $10^2 $ | $10^3 $ | 无 | | $3,4$ | $3000 $ | $3000 $ | $10^4 $ | 无 | | $5 \sim 7$ | $10^5 $ | $0 $ | $3 \times 10^5$ | 无 | | $8 $ | $2 \times 10^5$ | $200 $ | $5 \times 10^5$ | 无 | | $9 \sim 10$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | $\mathrm{A B }$ | | $11$ | ^ | ^ | ^ | $\mathrm{A C }$ | | $12\sim 14$ | ^ | ^ | ^ | $\mathrm{A D }$ | | $15\sim 17$ | ^ | ^ | ^ | $\mathrm{E }$ | | $18,19$ | ^ | ^ | ^ | 无 | | $20$ | $2 \times 10^5$ | $2 \times 10^5$ | $5 \times 10^5$ | ^ | - 特殊性质 $\text{A}$：保证对于所有 $1 \leq i \leq n$，$s_i$ 均在 $\{0,1\}$ 中**独立均匀随机**生成。 - 特殊性质 $\text{B}$：保证所有的 $x_i$ 互不相同，且对于所有 $1 \leq i \leq q$，均有 $s_{x_i} = 1$。 - 特殊性质 $\text{C}$：保证所有的 $x_i$ 互不相同，且对于所有 $1 \leq i \leq q$，均有 $s_{x_i} = 0$。 - 特殊性质 $\text{D}$：保证对于所有 $1 \leq i \leq q$，$x_i$ 均在 $[1, n]$ 中**独立均匀随机**生成。 - 特殊性质 $\text{E}$：保证对于所有 $0 \leq i < q$，均有 $1 \leq k_i \leq 45$。 附加文件来自于 [QOJ](https://qoj.ac/contest/2316/problem/13084)。