题目描述

故园中的那几棵木棉，仍旧生长在小 $N$ 逐渐朦胧的记忆中。小 $N$ 对故园的记忆，可以用一个长度为 $n$ 的序列 $[a_0,a_1,\ldots,a_{n-1}]$ 表示。

故园中的每棵木棉，都形如一棵结点有标号的无根树。小 $N$ 对一棵木棉的印象，可以用她的故园记忆的一个区间 $[l,r)$ 描述：

• 这棵树的结点数目为 $k=r-l+2$，结点编号为 $0\sim k-1$。
• $[\min(a_l,k-1),\min(a_{l+1},k-1),\ldots,\min(a_{r-1},k-1)]$ 是这棵树的 Prüfer 序列，其中 Prüfer 序列的定义详见【提示】一节。

在回忆往事时，小 $N$ 也向你提出了 $m$ 次询问。其中第 $i$（$0\le i<m$）次询问为：

• 在故园记忆的区间 $[l_i,r_i)$ 所对应的木棉上，结点 $x_i,y_i$ 是否相邻？

【实现细节】

选手不需要，也不应该实现 main 函数。

选手需要确保提交的程序源文件包含头文件 kapok.h，即在程序开头加入以下代码：

#include "kapok.h"

选手需要在提交的程序源文件 kapok.cpp 中实现以下函数：

std::vector<bool> kapok(
    int c, int n, int m, std::vector<int> a, std::vector<int> l, std::vector<int> r, std::vector<int> x, std::vector<int> y
);

• $c,n,m$ 分别表示测试点编号、故园记忆序列的长度、询问次数，$c=0$ 表示该测试点为样例。
• $a$ 表示故园记忆序列。
• $l,r$ 分别表示每次询问所给定的区间的两个端点。
• $x,y$ 分别表示每次询问所给定的两个结点的编号。
• 该函数需要返回一个长度恰好为 $m$ 的序列 $f_0,f_1,\ldots,f_{m-1}$，其中 $f_i$（$0\le i<m$）表示第 $i$ 次询问的结果。
• 对于每个测试点，该函数会被评测程序调用恰好一次。 本试题目录下的 template_kapok.cpp 是提供的示例代码，选手可参考并实现自己的代码。

输入格式

【测试程序方式】

选手可以在本题目录下使用如下命令编译得到可执行文件：

g++ grader.cpp kapok.cpp -o kapok -O2 -std=c++14 -static

对于编译得到的可执行文件 kapok：

• 可执行文件将从标准输入读入以下格式的数据：
  • 第一行包含三个非负整数 $c,n,m$。
  • 第二行包含 $n$ 个非负整数 $a_0,a_1,\ldots,a_{n-1}$。
  • 第 $i+3$（$0\le i<m$）行包含四个非负整数 $l_i,r_i,x_i,y_i$。
• 可执行文件将输出以下格式的数据至标准输出：
  • 第 $i+1$（$0\le i<m$）行包含一个非负整数，其中 $0$ 表示 $f_i$ 为 false，$1$ 表示 $f_i$ 为 true。

输出格式

无

输入输出样例 #1

输入 #1

0 8 3
2 0 2 6 0 7 2 2
0 3 0 2
3 5 1 2
0 0 0 1

输出 #1

1
0
1

说明/提示

【样例 $1$ 解释】

• 区间 $[0,3)$ 对应的树有 $5$ 个结点，Prüfer 序列为 $[2,0,2]$，边集为 $\{(1,2),(0,3),(0,2),(2,4)\}$，因此结点 $0,2$ 相邻。
• 区间 $[3,5)$ 对应的树有 $4$ 个结点，Prüfer 序列为 $[3,0]$，边集为 $\{(1,3),(0,2),(0,3)\}$，因此结点 $1,2$ 不相邻。
• 区间 $[0,0)$ 对应的树有 $2$ 个结点，Prüfer 序列为空，唯一一条边为 $(0,1)$，因此结点 $0,1$ 相邻。

【样例 $2$】

见选手目录下的 kapok/kapok2.in 与 kapok/kapok2.ans。

该样例满足测试点 $3\sim5$ 的约束条件。

【样例 $3$】

见选手目录下的 kapok/kapok3.in 与 kapok/kapok3.ans。

该样例满足测试点 $3\sim5$ 的约束条件。

【数据范围】

对于所有测试数据，均有：

• $1\le n,m\le2\times10^5$。
• 对于所有 $0\le i<n$，均有 $0\le a_i<n+2$。
• 对于所有 $0\le i<m$，均有 $0\le l_i\le r_i\le n$ 且 $0\le x_i,y_i<r_i-l_i+2$。

::cute-table{tuack}

特殊性质 $A$：对于所有 $0\le i<m$，在给定 $l_i,r_i$ 后，$(x_i,y_i)$ 均从所有满足限制的有序点对中独立均匀随机生成。

【提示】

对于一棵结点编号为 $0\sim c-1$（$c\ge2$）的无根树 $T$：

• 依次执行 $c-2$ 次操作，其中第 $i$（$0\le i<c-2$）次操作如下：
  • 找出当前编号最小的叶子 $v_i$。
  • 记录其唯一相邻点的编号 $p_i$。
  • 然后从 $T$ 中删去 $v_i$ 及其唯一邻边。
• 如此得到的长度为 $c-2$ 的序列 $[p_0,p_1,\ldots,p_{c-3}]$，即为 $T$ 的 Prüfer 序列。

附件下载 kapok.zip 566.91KB