CF1290C Prefix Enlightenment

有 $n$ 盏灯排成一行，编号从 $1$ 到 $n$。每盏灯初始状态为关（$0$）或开（$1$）。 你得到了 $k$ 个子集 $A_1, \ldots, A_k$，每个子集都是 $\{1, 2, \dots, n\}$ 的子集，且任意三个子集的交集为空。换句话说，对于所有 $1 \le i_1 < i_2 < i_3 \le k$，都有 $A_{i_1} \cap A_{i_2} \cap A_{i_3} = \varnothing$。 每次操作，你可以选择这 $k$ 个子集中的一个，将该子集内所有灯的状态切换（开变关，关变开）。保证对于给定的这些子集，经过若干次这样的操作后，可以使所有灯同时处于开状态。 令 $m_i$ 表示使前 $i$ 盏灯（即第 $1$ 到第 $i$ 盏）同时处于开状态所需的最少操作次数。注意，对于第 $i+1$ 到第 $n$ 盏灯的状态没有要求，它们可以是开也可以是关。 你需要计算所有 $1 \le i \le n$ 的 $m_i$。

第一行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 3 \cdot 10^5$）。 第二行包含一个长度为 $n$ 的二进制字符串，表示每盏灯的初始状态（若第 $i$ 盏灯为关，则 $s_i = 0$，为开则 $s_i = 1$）。 接下来是 $k$ 个子集的描述，每个子集的描述格式如下： 第一行包含一个整数 $c$（$1 \le c \le n$），表示该子集包含的元素个数。 第二行包含 $c$ 个互不相同的整数 $x_1, \ldots, x_c$（$1 \le x_i \le n$），表示该子集包含的元素编号。 保证： - 任意三个子集的交集为空； - 存在一种操作方案可以使所有灯同时处于开状态。

输出 $n$ 行，第 $i$ 行输出一个整数 $m_i$，表示使第 $1$ 到第 $i$ 盏灯同时处于开状态所需的最少操作次数。

在第一个样例中： - 对于 $i = 1$，只需对 $A_1$ 操作一次，最终状态为 $1010110$； - 对于 $i = 2$，对 $A_1$ 和 $A_3$ 各操作一次，最终状态为 $1100110$； - 对于 $i \ge 3$，对 $A_1$、$A_2$ 和 $A_3$ 各操作一次，最终状态为 $1111111$。 在第二个样例中： - 对于 $i \le 6$，只需对 $A_2$ 操作一次，最终状态为 $11111101$； - 对于 $i \ge 7$，对 $A_1$、$A_3$、$A_4$、$A_6$ 各操作一次，最终状态为 $11111111$。 由 ChatGPT 4.1 翻译