← 返回题目列表

Codeforces · 1290/C

C. 前缀启示

中文机器翻译题面 查看原题

一条线上有 $$$n$$$ 个灯,编号从 $$$1$$$ 到 $$$n$$$。每个都有一个初始状态关闭($$$0$$$)或打开($$$1$$$)。

给定您 $$$\{1, 2, \dots, n\}$$$ 的 $$$k$$$ 个子集 $$$A_1, \ldots, A_k$$$,使得任意三个子集的交集为空。换句话说,对于所有 $$$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$$$ 第一盏灯同时亮起所需执行的最少操作数。请注意,其他灯的状态没有任何条件($$$i+1$$$ 和 $$$n$$$ 之间),它们可以关闭或打开。

您必须为所有 $$$1 \le i \le n$$$ 计算 $$$m_i$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 3 \cdot 10^5$$$)。

第二行包含长度为 $$$n$$$ 的二进制字符串,表示每个灯的初始状态(如果 $$$s_i = 0$$$,则灯 $$$i$$$ 关闭,如果 $$$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$$$ 同时打开所需的最少操作数。

示例

输入 #1

7 3
0011100
3
1 4 6
3
3 4 7
2
2 3

输出 #1

1
2
3
3
3
3
3

输入 #2

8 6
00110011
3
1 3 8
5
1 2 5 6 7
2
6 8
2
3 5
2
4 7
1
2

输出 #2

1
1
1
1
1
1
4
4

输入 #3

5 3
00011
3
1 2 3
1
4
3
3 4 5

输出 #3

1
1
1
1
1

输入#4

19 5
1001001001100000110
2
2 3
2
5 6
2
8 9
5
12 13 14 15 16
1
19

输出#4

0
1
1
1
2
2
2
3
3
3
3
4
4
4
4
4
4
4
5

注意

在第一个示例中:

- 对于$$$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$$$。