#8180. 「省选联考 2024」 最长待机 NOI/NOI+/CTSC

时间限制:1000 ms 内存限制:128 MiB 输入文件:sleep.in 输出文件:sleep.out
题目类型:传统 评测方式:文本比较
上传者: root

注意

本题采用文件输入输出。

输入文件为 sleep.in, 输出文件为sleep.out

题目描述

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

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

  • 程序由 个函数组成,第 个函数具有种类 和子函数编号序列 可以为空,此时

  • 以及所有的 可以由程序员任意给出,但它们需要满足以下所有条件:

    • 中元素两两不同且均为 中的整数;
    • 恰好有一个 包含了
  • 调用函数 时,按顺序执行如下操作:

    • ,令变量 ;否则程序员需要立即为 输入一个正整数值
    • 为空,程序等待 秒;否则重复以下操作 次:
      • 按顺序调用编号为 的函数。
  • 若一个种类为 的函数 被调用多次,则其每次调用都需要输入

  • 我们认为,在函数调用中,除了“等待 秒”之外的操作不消耗任何时间,即函数调用、运行和输入都在瞬间完成。因此,一个时刻内程序员可能输入多个数。

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

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

  • 和 小 准备好各自的 Sleep++ 程序并选择各自程序中的一个函数。它们互相知晓对方程序的结构以及选择的函数。

  • 在时刻 ,小 和 小 同时调用自己选择的函数,游戏开始。

  • 在时刻 ),双方可以看到对方在时刻 输入的所有数字,并相应调整自己在时刻 输入的数字,但双方无法得知对方在时刻 输入的数字。

  • 函数调用先结束的一方输掉游戏,另一方胜利。两个调用同时结束算作平局。

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

写了一个 个函数的 Sleep++ 程序并进行了 次操作,操作有以下两种:

  • 操作一:给出 ,将 修改为
  • 操作二:给出 ,与小 玩一局“最长待机”,开始时小 会调用自己的函数

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

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

输入格式

从文件 sleep.in 中读入数据。

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

接下来 行,第 行若干个整数,描述小 程序中的函数

  • 前两个整数 表示函数种类和子函数编号序列长度;
  • 接下来 个整数 描述子函数编号序列。

接下来 行,第 行两个整数 描述一次操作,其中 表示操作一, 表示操作二。

输出格式

输出到文件 sleep.out 中。

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

样例

样例输入 1

3 6
0 2 2 3
0 0
0 0
2 1
1 3
2 1
1 3
1 2
2 1

样例输出 1

3
3
1

数据范围与提示

【样例 1 解释】

  • 对于前两次游戏,小 可以给出与小 完全一致的程序并在游戏开始时调用函数 。可以证明不存在函数个数更少的方案。

  • 对于第三次游戏,小 可以给出一个仅包含一个种类为 的函数的程序,并在游戏开始时调用函数

    • 在时刻 ,小 输入其程序中的 ,小 输入其程序中的
      • 注意: 变量在小 和小 的程序之间是独立的,不会互相影响。
    • 输入完成后,小 的程序在时刻 结束,小 的程序在时刻 结束。
    • 由于两人在时刻 互不知道对方的决策,不能保证 的大小关系,故双方均不存在必胜策略,这局游戏是公平的。

【样例 2】

见附件中的 sleep2.in/ans

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

【样例 3】

见附件中的 sleep3.in/ans

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

【样例 4】

见附件中的 sleep4.in/ans

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

【样例 5】

见附件中的 sleep5.in/ans

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

【子任务】

对于所有测试数据,

  • ,恰好有一个 包含了
测试点编号 特殊性质
AD
BD
D
AD
BD
D
A
BC
B
C
A
BC
B
C

特殊性质 A:保证

  • 任意时刻 均为
  • 操作二的 均为

特殊性质 B:保证

  • 操作二的 满足当时的

特殊性质 C:保证

  • ,序列 单调递增。

特殊性质 D:保证

  • 操作二不超过 个;
  • 操作二的 均为