AdditionalFile5765.zip

#5765. 「NOI2026」木棉

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

故园中的那几棵木棉，仍旧生长在小 $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

输入

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

输出

1
0
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$。

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

提示

对于一棵结点编号为 $0\sim c-1$ $(c\ge 2)$ 的无根树 $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 序列。