P17273 [eJOI 2026] Automata
题目描述
有一片由 $N$ 个格子排成一行的场地，从左到右编号为 $0$ 到 $N-1$。每个格子的高度互不相同：格子 $i$ 的高度为 $p_i$，序列 $p_0,p_1,\ldots,p_{N-1}$ 是 $0,1,\ldots,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,\ldots,x_{K_i-1}$ 组成的集合。机器人会被放在其中某个格子上，但具体是哪一个事先未知。对于每次询问，请判断是否存在一个程序，使得无论选中哪个起始格子，机器人最终都会到达同一个格子。
形式化地，你需要判断是否存在程序 $S$，满足
$$\operatorname{result}(S,x_0)=\operatorname{result}(S,x_1)=\cdots=\operatorname{result}(S,x_{K_i-1}).$$
所有询问使用同一个排列 $p$。
你不需要构造这样的程序，只需报告它是否存在。
### 实现细节
你需要实现以下两个函数：
```cpp
void initialize(std::vector p)
```
- $p$：$0$ 到 $N-1$ 的一个排列。
```cpp
bool exists_program(std::vector x)
```
- $x$：一次询问给出的格子，按严格递增顺序排列。
函数 `initialize` 恰好调用一次，并且发生在所有 `exists_program` 调用之前。
函数 `exists_program` 共调用 $Q$ 次，每次询问调用一次。如果存在某个程序，使得机器人无论从给定的哪个格子出发，最终都会停在同一个格子，则应返回 `true`；否则返回 `false`。
输入格式
输入格式：
- 第 $1$ 行：两个整数 $N$ 和 $Q$；
- 第 $2$ 行：$N$ 个整数 $p_0,p_1,\ldots,p_{N-1}$，其中 $p_i$ 表示格子 $i$ 的高度；
- 第 $3+i$ 行：一个整数 $K_i$，随后是 $K_i$ 个整数 $x_0,x_1,\ldots,x_{K_i-1}$，描述第 $i$ 次询问。
输出格式
输出格式：
- 第 $1$ 行：一个长度为 $Q$ 的二进制串。若第 $i$ 次询问的答案为 `true`，则第 $i$ 个字符为 `1`，否则为 `0`。
说明/提示
### 样例 1 解释
本例中 $p=[0,2,1]$。对于第二次询问，机器人可能从格子 $0$、$1$ 或 $2$ 出发。考虑程序 $[\texttt{MAX}]$。
- 若从格子 $0$ 出发，与其接近的是格子 $0$ 和 $1$。由于 $p_0p_2$，机器人移动到格子 $1$。
因此存在一个程序，使机器人从三个起点出发最终都停在格子 $1$，答案为 `true`。其他可行程序包括 $[\texttt{MIN},\texttt{MAX}]$、$[\texttt{MIN},\texttt{MIN},\texttt{MAX},\texttt{MIN},\texttt{MAX},\texttt{MIN}]$ 和 $[\texttt{MAX},\texttt{MIN},\texttt{MAX}]$。
### 样例 2 解释
本例中 $p=[0,4,2,1,3,5,6]$。
对于前两次询问，不存在能让机器人从所有给定起点出发后停在同一格子的程序，因此两个答案均为 `false`。
对于最后一次询问，机器人可能从格子 $3$ 或 $6$ 出发。考虑程序 $[\texttt{MAX},\texttt{MAX},\texttt{MAX}]$。
- 若从格子 $3$ 出发，与其接近的是格子 $2$、$3$ 和 $4$。由于 $p_3