4343. [国家集训队 2026]复读机

【题目描述】

考虑两位玩家进行如下的一个信任游戏（请注意，这个游戏可能与你所了解的某游戏有所不同）：

- 有一台这样的机器：当一位玩家放进去一枚硬币，另一位玩家会得到三枚硬币。

- 游戏共进行 $2m$ 轮，两位玩家轮流行动，每次行动中，行动的玩家可以选择一下两种操作其一：

 - 「合作」：放入一枚硬币；

 - 「欺骗」：不放硬币。

- 若选择「合作」，则行动的玩家失去一枚硬币，另一位玩家获得三枚硬币；若选择「欺骗」，则无事发生。

- 每次行动后，另一位玩家会获知当前行动玩家的选择。

现在你将和「复读机」进行这个信任游戏，你先行动。「复读机」的策略可以用若干个长度不超过 $m$ 的 01 串构成的可重集合 $S$ 表示。他的具体策略为：先从集合中等概率随机选取一个 01 串 $s$，设其长度为 $k$，则他在第 $2i$ ($1 \le i \le m$) 轮（也就是他的第 $i$ 次行动）时策略为：

 - 对于 $1 \le i \le k$，若 $s_i = 0$，则选择「合作」；若 $s_i = 1$，选择「欺骗」。

 - 对于 $k < i \le m$，选择与你的上一次选择相同，也就是第 $2i-1$ 轮的选择。

现在你的对手「复读机」的策略池 $S$ 还未确定，他会进行 $n$ 次操作：每次操作包含一个长度不超过 $m$ 的 01 串 $s_i$ 和数量 $a_i$，表示向 $S$ 中加入 $a_i$ 个 $s_i$。特别地，如果 $a_i < 0$，则表示从 $S$ 中删除 $-a_i$ 个 $s_i$，其中 $S$ 中至少有 $-a_i$ 个 $s_i$，且删除后 $S$ 中至少还有 1 个 01 串。

你需要在每次操作后，计算出你在最优策略下，期望最多收益为多少硬币，每次操作后的询问相互独立。请注意，你已知集合 $S$，但你并不能得知他选择的 01 串 $s$，而你的每次行动都可以基于之前轮双方的选择进行决策。你只需要输出期望收益乘 $|S|$ 的值，可以证明是一个整数。

【输入格式】

输入的第一行包含两个正整数 $n, m$。

输入的第 $i+1$ ($1 \le i \le n$) 包含一个长度不超过 $m$ 的 01 串 $s_i$ 和一个整数 $a_i$。

【输出格式】

输出 $n$ 行，每行一个整数表示答案。

【样例输入】

8 3
111 1
1 1
0 1
011 4
1 -1
01 3
011 -3
0 3

【样例输出】

0
3
10
18
15
28
22
41

【数据规模与约定】

对于所有测试数据，均有：

- $1 \le n \le 3 \times 10^5$，$1 \le m \le 10^6$；

- 对于所有 $1 \le i \le n$，均有 $1 \le |s_i| \le m$，$1 \le |a_i| \le 10^6$，且 $\sum_{i=1}^{n} |s_i| \le 4 \times 10^5$。

- 对于所有 $1 \le i \le n$，若 $a_i < 0$，则 $S$ 中至少有 $-a_i$ 个 $s_i$，且删除后 $S$ 中至少还有 1 个 01 串。

特殊性质 A：对于所有 $1 \le i \le n$，均有 $a_i = 1$，且 $\sum_{i=1}^{n} |s_i| \le 5000$。

特殊性质 B：对于所有 $1 \le i < n$，均有 $|s_i| \ge |s_{i+1}|$。

【评分方式】

对于每个子任务：

1. 正确回答所有测试数据的第 $n$ 次操作后的答案，可获得该子任务 $40\%$ 的分数；

2. 正确回答所有测试数据的答案，可获得该子任务 $100\%$ 的分数。

注意：即使选手仅回答了第 $n$ 次操作后的答案，也需要按照输出格式输出 $n$ 个整数，分别对应每次操作后的答案。

原题共$126$组测试数据，COGS只有$100$组，你必须完全回答正确才能得分，剩余测试数据下载：第101-126组数据。

【来源】

IOI2026中国国家集训队集中培训 Day3 Task2