【统一省选2024】最长待机 - 题目

精灵程序员小 $\omega$ 和小 $\aleph$ 拥有无限的寿命，因此在写代码之余，它们经常玩一些对抗游戏来打发时间。尽管如此，时间还是太多，于是它们发明了一款专用于消磨时间的游戏：最长待机。

为了了解最长待机的规则，首先要了解精灵们使用的编程语言 Sleep++ 的规则：

程序由 $n$ 个函数组成，第 $i(1 \le i\le n)$ 个函数具有种类 $e_i$ 和子函数编号序列 $Q_i = (Q_{i,1},Q_{i,2},\cdots,Q_{i,l_i})$。$Q_i$ 可以为空，此时 $l_i$ 为 $0$。
$n$ 以及所有的 $e_i$ 和 $Q_i$ 可以由程序员任意给出，但它们需要满足以下所有条件：
- $n\ge 1$；
- $\forall 1 \le i \le n$，$e_i \in \{0, 1\}$；
- $\forall 1 \le i \le n$，$Q_i$ 中元素两两不同且均为 $[i + 1, n]$ 中的整数；
- $\forall 2 \le j \le n$，恰好有一个 $Q_i(1 \le i \le n)$ 包含了 $j$。
调用函数 $i(1 \le i \le n)$ 时，按顺序执行如下操作：
- 若 $e_i = 0$，令变量 $r_i$ 为 $1$；否则程序员需要立即为 $r_i$ 输入一个正整数值。
- 若 $Q_i$ 为空，程序等待 $r_i$ 秒；否则重复以下操作 $r_i$ 次：
  - 按顺序调用编号为 $Q_{i,1},Q_{i,2},\cdots,Q_{i,l_i}$ 的函数。
若一个种类为 $1$ 的函数 $j$ 被调用多次，则其每次调用都需要输入 $r_j$。
我们认为，在函数调用中，除了“等待 $r$ 秒”之外的操作不消耗任何时间，即函数调用、运行和输入都在瞬间完成。因此，一个时刻内程序员可能输入多个数。

可以证明，调用任意一个 Sleep++ 程序的任意一个函数，无论如何设定输入，消耗的时间总是有限的。

“最长待机”的游戏规则如下：

小 $\omega$ 和小 $\aleph$ 准备好各自的 Sleep++ 程序并选择各自程序中的一个函数。它们互相知晓对方程序的结构以及选择的函数。
在时刻 $0$，小 $\omega$ 和小 $\aleph$ 同时调用自己选择的函数，游戏开始。
在时刻 $t$（$t \ge 0$），双方可以看到对方在时刻 $0$ 至 $(t - 1)$ 输入的所有数字，并相应调整自己在时刻 $t$ 输入的数字，但双方无法得知对方在时刻 $t$ 输入的数字。
函数调用先结束的一方输掉游戏，另一方胜利。两个调用同时结束算作平局。

小 $\omega$ 和小 $\aleph$ 都是绝顶聪明的，在它们眼中，如果有一方存在必胜策略，那么这局游戏是不公平的。换言之，双方都不存在必胜策略的游戏是公平的。

小 $\omega$ 写了一个 $n$ 个函数的 Sleep++ 程序并进行了 $m$ 次操作，操作有以下两种：

操作一：给出 $k$，将 $e_k$ 修改为 $(1 - e_k)$；
操作二：给出 $k$，与小 $\aleph$ 玩一局“最长待机”，开始时小 $\omega$ 会调用自己的函数 $k$。

小 $\aleph$ 信奉极简主义，它希望对于每一局游戏设计出函数个数最少的程序，使得选择其中某个函数能让这局游戏是公平的。你能帮它求出最少所需的函数个数吗？

可以证明，小 $\aleph$ 总是能设计一个程序并选择其中一个函数，使得游戏是公平的。

输入格式

输入的第一行包含两个正整数 $n,m$，表示小 $\omega$ 的程序中函数的个数以及操作次数。

接下来 $n$ 行，第 $i$ 行若干个整数，描述小 $\omega$ 程序中的函数 $i$：

前两个整数 $e_i, l_i$ 表示函数种类和子函数编号序列长度；
接下来 $l_i$ 个整数 $Q_{i,1},Q_{i,2},\cdots,Q_{i,l_i}$ 描述子函数编号序列。

接下来 $m$ 行，第 $j$ 行两个整数 $o_j, k_j$ 描述一次操作，其中 $o_j = 1$ 表示操作一，$o_j = 2$ 表示操作二。

输出格式

对于每个操作二输出一行一个整数，表示小 $\aleph$ 的程序中最少所需的函数个数。

样例 #1

样例输入 #1

样例输出 #1

3
3
1

提示

【样例 1 解释】

对于前两次游戏，小 $\aleph$ 可以给出与小 $\omega$ 完全一致的程序并在游戏开始时调用函数 $1$。可以证明不存在函数个数更少的方案。
对于第三次游戏，小 $\aleph$ 可以给出一个仅包含一个种类为 $1$ 的函数的程序，并在游戏开始时调用函数 $1$。
- 在时刻 $0$，小 $\omega$ 输入其程序中的 $r_2$，小 $\aleph$ 输入其程序中的 $r_1$。
  - 注意：$r$ 变量在小 $\omega$ 和小 $\aleph$ 的程序之间是独立的，不会互相影响。
- 输入完成后，小 $\omega$ 的程序在时刻 $(r_2 +1)$ 结束，小 $\aleph$ 的程序在时刻 $r_1$ 结束。
- 由于两人在时刻 $0$ 互不知道对方的决策，不能保证 $(r_2 + 1)$ 和 $r_1$ 的大小关系，故双方均不存在必胜策略，这局游戏是公平的。

【样例 2】

见附件中的 sleep2.in/ans。

该组数据满足特殊性质 AD。

【样例 3】

见附件中的 sleep3.in/ans。

该组数据满足特殊性质 BD。

【样例 4】

见附件中的 sleep4.in/ans。

该组数据满足特殊性质 D。

【样例 5】

见附件中的 sleep5.in/ans。

该组数据满足特殊性质 C。

【子任务】

对于所有测试数据，

$1 \le n \le 5\times 10^5$，$1 \le m \le 2\times 10^5$；
$\forall 1 \le i \le n$，$e_i\in \{0, 1\}$，$0 \le l_i
$\forall 1 \le i \le n,1 \le j \le l_i$，$i < Q_{i,j} \le n$；
$\forall 1 \le i \le n, 1 \le p < q \le l_i$，$Q_{i,p}\neq Q_{i,q}$；
$\forall 2 \le j \le n$，恰好有一个 $Q_i(1 \le i \le n)$ 包含了 $j$；
$\forall 1 \le j \le m$，$1 \le o_j \le 2$，$1 \le k_j \le n$。

测试点编号	$n \le $	$m\le $	特殊性质
$1\sim 2$	$3$	$24$	无
$3$	$80$	$400$	AD
$4$	$80$	$400$	BD
$5\sim 6$	$80$	$400$	D
$7$	$3\times 10^5$	$10^5$	AD
$8$	$3\times 10^5$	$10^5$	BD
$9\sim 10$	$3\times 10^5$	$10^5$	D
$11$	$3\times 10^5$	$10^5$	A
$12$	$3\times 10^5$	$10^5$	BC
$13$	$3\times 10^5$	$10^5$	B
$14\sim 15$	$3\times 10^5$	$10^5$	C
$16\sim 17$	$3\times 10^5$	$10^5$	无
$18\sim 19$	$5\times 10^5$	$2\times 10^5$	A
$20$	$5\times 10^5$	$2\times 10^5$	BC
$21$	$5\times 10^5$	$2\times 10^5$	B
$22\sim 23$	$5\times 10^5$	$2\times 10^5$	C
$24\sim 25$	$5\times 10^5$	$2\times 10^5$	无

特殊性质 A：保证

任意时刻 $e_1$ 均为 $0$；
$\forall 2\le i \le n$，$l_i \le 1$；
操作二的 $k$ 均为 $1$。

特殊性质 B：保证

操作二的 $k$ 满足当时的 $e_k$ 为 $1$。

特殊性质 C：保证

$\forall 2\le i \le n$，$i \in Q_{\lfloor \frac{i}{2}\rfloor}$；
$\forall 1 \le i \le n$，序列 $Q_i$ 单调递增。

特殊性质 D：保证

操作二不超过 $10$ 个；
操作二的 $k$ 均为 $1$。

时间限制：2s $\texttt{3.5s}$

空间限制：$\texttt{1024MB}$

Universal Online Judge

UOJ

#870. 【统一省选2024】最长待机

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示