负责人

• SleepingCup

题目描述

小 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 能达成获胜目标。

样例

0 3
5 1
01010
4
7 0
0001000
10 0
0001010000

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】

见选手目录下的 defense/defense2.in 与 defense/defense2.ans。

该样例满足测试点 $2$ 的约束条件。

【样例 3】

见选手目录下的 defense/defense3.in 与 defense/defense3.ans。

该样例满足测试点 $5 \sim 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 \sim 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$		$60$	无
$2$	$10^2$		$10^3$
$3,4$	$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$		$3 \times 10^5$	$\mathrm{A B }$
$11$	$10^5$			$\mathrm{A C }$
$12\sim 14$				$\mathrm{A D }$
$15\sim 17$				$\mathrm{E }$
$18,19$				无
$20$	$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。