P14932 [北大集训 2025] 复读机

考虑两位玩家进行如下的一个信任游戏（请注意，这个游戏可能与你所了解的某游戏有所不同）： - 有一台这样的机器：当一位玩家放进去一枚硬币，另一位玩家会得到三枚硬币。 - 游戏共进行 $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$ 行，每行一个整数表示答案。

### 【子任务】 对于所有测试数据，均有： - $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 串。 | 子任务编号 | 分值 | $n \le$ | $m \le$ | 特殊性质 | |:-:|:-:|:-:|:-:|:-:| | 1 | 20 | $2000$ | $2000$ | A | | 2 | 15 | $20$ | $10^6$ | 无 | | 3 | 15 | $3 \times 10^5$ | $20$ | 无 | | 4 | 15 | $3 \times 10^5$ | $10^6$ | B | | 5 | 35 | $3 \times 10^5$ | $10^6$ | 无 | 特殊性质 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$ 个整数，分别对应每次操作后的答案。