A5083. [NOI2025] 绝对防御
编程题
NOI/NOI+/CTSC
知识点
题目描述
小 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 能达成胜利目标。
小 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$ 张牌。
输入的第一行包含两个非负整数 $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
0 3 5 1 01010 4 7 0 0001000 10 0 0001010000
输出 #1
1 1 3 2
说明/提示
#### 【样例 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】
该样例满足测试点 2 的约束条件。
【样例 3】
该样例满足测试点 5 ~ 7 的约束条件。
【样例 4】
该样例满足测试点 9,10 的约束条件。
【样例 5】
该样例满足测试点 11 的约束条件。
【样例 6】
该样例满足测试点 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$。
| 测试点编号 | $n \leq$ | $q \leq$ | $N, Q \leq$ | 特殊性质 |
|------------|----------|----------|-------------|----------|
| $1 $ | $20 $ | $20 $ | $60 $ | 无 |
| $2 $ | $10^2 $ | $10^2 $ | $10^3 $ | 无 |
| $3 $ | $3000 $ | $3000 $ | $10^4 $ | 无 |
| $4 $ | $3000 $ | $3000 $ | $10^4 $ | 无 |
| $5 $ | $10^5 $ | $0 $ | $3 \times 10^5$ | 无 |
| $6 $ | $10^5 $ | $0 $ | $3 \times 10^5$ | 无 |
| $7 $ | $10^5 $ | $0 $ | $3 \times 10^5$ | 无 |
| $8 $ | $2 \times 10^5$ | $200 $ | $5 \times 10^5$ | 无 |
| $9 $ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | $\mathrm{A B }$ |
| $10$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | $\mathrm{A B }$ |
| $11$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | $\mathrm{A C }$ |
| $12$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | $\mathrm{A D }$ |
| $13$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | $\mathrm{A D }$ |
| $14$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | $\mathrm{A D }$ |
| $15$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | $\mathrm{E }$ |
| $16$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | $\mathrm{E }$ |
| $17$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | $\mathrm{E }$ |
| $18$ | $2 \times 10^5$ | $2 \times 10^5$ | $5 \times 10^5$ | 无 |
| $19$ | $2 \times 10^5$ | $2 \times 10^5$ | $5 \times 10^5$ | 无 |
| $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$。
该样例共包含三组测试数据。
对于第一组测试数据：
- 初始时，牌堆为 $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】
该样例满足测试点 2 的约束条件。
【样例 3】
该样例满足测试点 5 ~ 7 的约束条件。
【样例 4】
该样例满足测试点 9,10 的约束条件。
【样例 5】
该样例满足测试点 11 的约束条件。
【样例 6】
该样例满足测试点 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$。
| 测试点编号 | $n \leq$ | $q \leq$ | $N, Q \leq$ | 特殊性质 |
|------------|----------|----------|-------------|----------|
| $1 $ | $20 $ | $20 $ | $60 $ | 无 |
| $2 $ | $10^2 $ | $10^2 $ | $10^3 $ | 无 |
| $3 $ | $3000 $ | $3000 $ | $10^4 $ | 无 |
| $4 $ | $3000 $ | $3000 $ | $10^4 $ | 无 |
| $5 $ | $10^5 $ | $0 $ | $3 \times 10^5$ | 无 |
| $6 $ | $10^5 $ | $0 $ | $3 \times 10^5$ | 无 |
| $7 $ | $10^5 $ | $0 $ | $3 \times 10^5$ | 无 |
| $8 $ | $2 \times 10^5$ | $200 $ | $5 \times 10^5$ | 无 |
| $9 $ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | $\mathrm{A B }$ |
| $10$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | $\mathrm{A B }$ |
| $11$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | $\mathrm{A C }$ |
| $12$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | $\mathrm{A D }$ |
| $13$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | $\mathrm{A D }$ |
| $14$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | $\mathrm{A D }$ |
| $15$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | $\mathrm{E }$ |
| $16$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | $\mathrm{E }$ |
| $17$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | $\mathrm{E }$ |
| $18$ | $2 \times 10^5$ | $2 \times 10^5$ | $5 \times 10^5$ | 无 |
| $19$ | $2 \times 10^5$ | $2 \times 10^5$ | $5 \times 10^5$ | 无 |
| $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$。