#213397. [NOI2025] 绝对防御

defense.cpp / 4 s / 1024 MiB

小 Q 在与电脑玩一款名为“绝对防御”的回合制卡牌游戏。

小 Q 有一个大小为 的牌堆，包含两种牌：攻击牌与防御牌。游戏开始时，小 Q 会从牌堆顶抽取 张牌作为初始手牌，接下来他会与电脑进行若干轮对战。

每轮对战开始时，小 Q 从牌堆顶抽取 张牌。特别地，若牌堆只剩余 张牌，则小 Q 只抽取 张。一轮对战分为两个回合：

• 第一回合：小 Q 为攻击方，电脑为防御方；
• 第二回合：小 Q 为防御方，电脑为攻击方。

在每回合中，攻击方必须从手牌中选择一张攻击牌进行攻击，防御方必须从手牌打出一张防御牌进行防御。无法按要求出牌者立即判负。

电脑的攻击牌与防御牌都是无限的，即电脑总能打出对应牌。为平衡电脑的实力，小 Q 可以使用一种特殊技能：当小 Q 为防御方时，他可以从手牌打出一张攻击牌进行防御。该技能每 轮对战才能使用一次，即在某轮使用技能后，接下来的 轮对战中不能使用该技能。

在给定规则下，小 Q 的获胜目标为在电脑猛烈攻击中幸存，即在某轮对战结束后，牌堆被抽空。特别地，若游戏开始时牌堆已被抽空，则小 Q 直接达成获胜目标。小 Q 想知道最小的初始抽牌数 ，使得他能达成胜利目标。

小 Q 觉得这个问题过于简单，因此他增加了 次修改操作。第 次修改操作给定一个正整数 ，改变牌堆顶到牌堆底的第 张牌的类型，即将攻击牌变为防御牌，将防御牌变为攻击牌。你需要对初始牌堆及每次修改后的牌堆，求出最小的小 Q 初始抽牌数 ，使得小 Q 能达成胜利目标。

本题包含多组测试数据。

输入的第一行包含两个非负整数 ，分别表示测试点编号与测试数据组数。 表示测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

第一行包含两个非负整数 ，分别表示牌堆大小与修改次数。

第二行包含一个长度为 的字符串 ，分别表示从牌堆顶到底的每张牌，

其中 表示第 张牌为攻击牌， 表示第 张牌为防御牌。

第 行包含一个正整数 ，表示第 次修改的牌为从牌堆顶到牌堆底的第 张牌。

对于每组测试数据，设初始时的答案为 ，第 () 次修改后的答案为 ，输出一行 个正整数 ，表示初始时及每次修改后的最小抽牌数，使得小 Q 能达成获胜目标。

样例输入 1

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

样例输出 1

1 1
3
2

【样例 1 解释】

该样例共包含三组测试数据。

对于第一组测试数据：

• 初始时，牌堆为 。若初始抽牌数为 ，小 Q 的一种可能的出牌方式为：
  • 初始时手牌为 ;
  • 从堆顶抽取两张牌，打出一张攻击牌，一张防御牌，手牌变为 ;
  • 从堆顶抽取两张牌，打出一张攻击牌，一张防御牌，手牌变为 ，此时牌堆被抽空。

由于初始至少需要抽取一张牌，所以最小初始抽牌数为 ，故 。

• 第一次修改后，牌堆变为 。若初始抽牌数为 ，小 Q 的一种可能的出牌方式为：
  • 初始时手牌为 ;
  • 从堆顶抽取两张牌，打出一张攻击牌，一张防御牌，手牌变为 ;
  • 从堆顶抽取两张牌，打出一张攻击牌，使用特殊技能再次打出一张攻击牌进行防御，手牌变为 ，此时牌堆被抽空。

由于初始至少需要抽取一张牌，所以最小初始抽牌数为 1，故 。

对于第二组测试数据：

若初始抽牌数为 ，小 Q 的一种可能的出牌方式为：

• 初始时手牌为 ;
• 从堆顶抽取两张牌，打出一张攻击牌，一张防御牌，手牌变为 ;
• 从堆顶抽取两张牌，打出一张攻击牌，使用特殊技能再次打出一张攻击牌进行防御，手牌变为 ，此时牌堆被抽空。 可以证明，不存在比 更小的初始抽牌数能够抽空牌堆，故答案为 。

对于第三组测试数据：

若初始抽牌数为 ，小 Q 的一种可能的出牌方式为：

• 初始时手牌为 ;
• 从堆顶抽取两张牌，打出一张攻击牌，使用特殊技能再次打出一张攻击牌进行防御，手牌变为 ;
• 从堆顶抽取两张牌，打出一张攻击牌，一张防御牌，手牌变为 ;
• 从堆顶抽取两张牌，打出一张攻击牌，一张防御牌，手牌变为 ，此时牌堆被抽空。 可以证明，不存在比 更小的初始抽牌数能够抽空牌堆，故答案为 。

【样例 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 的约束条件。

数据范围

设 分别为单个测试点内所有测试数据的 的和。对于所有测试数据，保证：

• ；
• ，；
• ，；
• 对于所有 ，均有 ；
• 对于所有 ，均有 。

::cute-table{tuack}

• 特殊性质 ：保证对于所有 ， 均在 中独立均匀随机生成。
• 特殊性质 ：保证所有的 互不相同，且对于所有 ，均有 。
• 特殊性质 ：保证所有的 互不相同，且对于所有 ，均有 。
• 特殊性质 ：保证对于所有 ， 均在 中独立均匀随机生成。
• 特殊性质 ：保证对于所有 ，均有 。

附加文件来自于 QOJ。