A6756 | 「NOI2025」绝对防御

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

从文件 defense.in 中读入数据。

**本题包含多组测试数据**。

输入的第一行包含两个非负整数 $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$ 张牌。

输出到文件 defense.out 中。

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