• 比赛：EJOI 2026 Day 2
• 时间限制：2 秒
• 内存限制：1024 MiB
• 题目类型：函数提交题

题目描述

有一块由 $N$ 个格子组成的一维场地，从左到右编号为 $0$ 到 $N-1$。每个格子的高度互不相同，第 $i$ 个格子的高度为 $p_i$，且序列 $p_0,p_1,\dots,p_{N-1}$ 是 $0,1,\dots,N-1$ 的一个排列。

当且仅当 $|i-j|\le 1$ 时，称编号为 $i$ 和 $j$ 的两个格子彼此接近。特别地，每个格子都与自身接近。

一个机器人站在场地上的某个格子中。它能够接受两种命令：

• MAX：在所有与机器人当前位置接近的格子中，移动到高度最大的那个格子；
• MIN：在所有与机器人当前位置接近的格子中，移动到高度最小的那个格子。

因为当前位置本身也属于“接近”的格子，所以一条命令也可能使机器人保持不动。

一个程序是一段有限长的命令序列，其中每条命令均为 MAX 或 MIN。

若机器人从格子 $X$ 出发，按照程序 $S$ 执行，最终会到达唯一确定的格子，记作 $\operatorname{result}(S,X)$。

现在有 $Q$ 次询问。第 $i$ 次询问给出 $K_i$ 个可能的起始格子：

$x_0,x_1,\dots,x_{K_i-1}$。

机器人会从这些格子中的某一个出发，但你事先不知道具体是哪一个。

你需要判断：是否存在某个程序 $S$，使得无论机器人从给定的哪个起点出发，最终都会到达同一个格子。

也就是说，需要判断是否存在 $S$ 满足

$\operatorname{result}(S,x_0)=\operatorname{result}(S,x_1)=\cdots=\operatorname{result}(S,x_{K_i-1})$。

所有询问使用同一个排列 $p$。

你不需要构造这个程序，只需要判断它是否存在。

实现要求

你需要实现两个函数。

初始化函数

void initialize(std::vector<int> p);

• p：$0$ 到 $N-1$ 的一个排列。

该函数恰好调用一次，并且发生在所有 exists_program 调用之前。

询问函数

bool exists_program(std::vector<int> x);

• x：一次询问给出的所有起始格子，严格递增排列。

该函数共调用 $Q$ 次，每次对应一个询问。

若存在一个程序，使机器人从 x 中任意起点出发都能到达同一终点，则返回 true；否则返回 false。

数据范围

• $3\le N\le 2\cdot 10^5$；
• $1\le Q\le 5\cdot 10^5$；
• $p_0,p_1,\dots,p_{N-1}$ 是 $0,1,\dots,N-1$ 的一个排列；
• $2\le K_i\le N$；
• 对每次询问均有 $0\le x_0<x_1<\cdots<x_{K_i-1}<N$；
• 所有询问的 $K_i$ 之和不超过 $10^6$。

样例 1

Sample grader 输入

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

Sample grader 输出

111

说明

此时 $p=[0,2,1]$。

对于第二次询问，机器人可能从 $0,1,2$ 中任意一个位置出发。程序 [MAX] 即可使它们全部到达格子 $1$。

例如：

• 从 $0$ 出发，MAX 会将机器人移动到 $1$；
• 从 $1$ 出发，$p_1$ 比相邻格子都高，因此保持在 $1$；
• 从 $2$ 出发，MAX 会移动到 $1$。

因此答案为 true。

样例 2

Sample grader 输入

7 3
0 4 2 1 3 5 6
3 0 1 3
3 1 3 4
2 3 6

Sample grader 输出

001

说明

此时 $p=[0,4,2,1,3,5,6]$。

前两次询问不存在满足要求的程序。

最后一次询问的起点为 $3$ 和 $6$。程序 [MAX,MAX,MAX] 可以使两个起点最终都到达格子 $6$，因此答案为 true。

子任务

子任务	分值	$N$	$Q$	$K_i$	额外限制
0		-			样例
1	3	$\le2\cdot10^5$	$\le5\cdot10^5$	$=2$	若答案为真，则存在恰好使用 1 条命令的可行程序
2	7				若答案为真，则存在至多使用 5 条命令的可行程序
3	9	$\le100$	$\le500$		无
4	17	$\le5000$	$\le5\cdot10^5$
5	7	$\le2\cdot10^5$			每次询问均满足 $x_1=x_0+1$
6	8	$\le5000$		$\le N$	无
7	13	$\le2\cdot10^5$			排列先递增、再递减、再递增
8					排列相邻高低交替
9	23				无

子任务 7 中，存在 $0<a<b<N-1$，使得

$p_0<p_1<\cdots<p_a>p_{a+1}>\cdots>p_b<p_{b+1}<\cdots<p_{N-1}$。

子任务 8 中：

• 若 $N$ 为偶数，则 $p_0<p_1>p_2<p_3>\cdots<p_{N-1}$；
• 若 $N$ 为奇数，则 $p_0<p_1>p_2<p_3>\cdots>p_{N-1}$。

Sample grader

输入格式：

• 第一行两个整数 $N,Q$；
• 第二行 $N$ 个整数 $p_0,p_1,\dots,p_{N-1}$；
• 接下来 $Q$ 行，第 $i$ 行先给出 $K_i$，然后给出 $K_i$ 个整数 $x_0,\dots,x_{K_i-1}$。

输出一行长度为 $Q$ 的二进制串。第 $i$ 个字符为 1 表示第 $i$ 次询问返回 true，否则为 0。