Background

The statement and sample attachments come from QOJ。

When submitting to Luogu, there is no need to include the header #include "kapok.h"。Just copy

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
);

to the beginning of your program, and compile with a C++17 or higher compiler.

Problem Description

Those kapok trees in the old home are still growing in Little $N$'s gradually blurred memories. Little $N$'s memories of the old home can be represented by a sequence of length $n$, $[a_0,a_1,\ldots,a_{n-1}]$。

Each kapok tree in the old home is an unrooted tree with labeled nodes. Little $N$'s impression of a kapok tree can be described by an interval $[l,r)$ of her old-home memory:

• This tree has $k=r-l+2$ nodes, with node labels $0\sim k-1$。
• $[\min(a_l,k-1),\min(a_{l+1},k-1),\ldots,\min(a_{r-1},k-1)]$ is the Prüfer sequence of this tree, where the definition of Prüfer sequence is given in the [Hint] section.

While recalling the past, Little $N$ also asked you $m$ queries. The $i$-th query ($0\le i<m$) is:

• On the kapok tree corresponding to the interval $[l_i,r_i)$ in the old-home memory, are nodes $x_i,y_i$ adjacent?

Implementation Details

Contestants do not need to, and should not, implement the main function.

Contestants need to ensure that the submitted source file includes the header kapok.h, i.e. add the following code at the beginning:

#include "kapok.h"

Contestants need to implement the following function in the submitted source file 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$ represent the test point index, the length of the old-home memory sequence, and the number of queries, respectively. $c=0$ means this test point is a sample.
• $a$ is the old-home memory sequence.
• $l,r$ are the two endpoints of the interval given in each query.
• $x,y$ are the labels of the two nodes given in each query.
• This function needs to return a sequence of length exactly $m$, $f_0,f_1,\ldots,f_{m-1}$, where $f_i$ ($0\le i<m$) is the answer to the $i$-th query.
• For each test point, this function will be called exactly once by the judge. template_kapok.cpp in this problem directory is the provided sample code. Contestants may refer to it and implement their own code.

Input Format

Test Program Method

Contestants can compile an executable in this problem directory using the following command:

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

For the compiled executable kapok:

• The executable will read input from standard input in the following format:
  • The first line contains three non-negative integers $c,n,m$。
  • The second line contains $n$ non-negative integers $a_0,a_1,\ldots,a_{n-1}$。
  • The $(i+3)$-th line ($0\le i<m$) contains four non-negative integers $l_i,r_i,x_i,y_i$。
• The executable will output to standard output in the following format:
  • The $(i+1)$-th line ($0\le i<m$) contains one non-negative integer, where $0$ means $f_i$ is false, and $1$ means $f_i$ is true。

Output Format

Hint

Sample $1$ Explanation

• The tree corresponding to interval $[0,3)$ has $5$ nodes, and its Prüfer sequence is $[2,0,2]$. The edge set is $\{(1,2),(0,3),(0,2),(2,4)\}$. Therefore, nodes $0,2$ are adjacent.
• The tree corresponding to interval $[3,5)$ has $4$ nodes, and its Prüfer sequence is $[3,0]$. The edge set is $\{(1,3),(0,2),(0,3)\}$. Therefore, nodes $1,2$ are not adjacent.
• The tree corresponding to interval $[0,0)$ has $2$ nodes, and its Prüfer sequence is empty. The only edge is $(0,1)$. Therefore, nodes $0,1$ are adjacent.

Sample $2$

See kapok/kapok2.in and kapok/kapok2.ans in the contestants' directory.

This sample satisfies the constraints of test points $3\sim5$。

Sample $3$

See kapok/kapok3.in and kapok/kapok3.ans in the contestants' directory.

This sample satisfies the constraints of test points $3\sim5$。

Constraints

For all testdata:

• $1\le n,m\le2\times10^5$。
• For all $0\le i<n$, $0\le a_i<n+2$。
• For all $0\le i<m$, $0\le l_i\le r_i\le n$ and $0\le x_i,y_i<r_i-l_i+2$。

::cute-table{tuack} | Test point index | $n,m\le$ | Special property | |:-:|:-:|:-:| | $1,2$ | $500$ | None | | $3\sim5$ | $5000$ | ^ | | $6,7$ | $2\times10^5$ | For all $0\le i<n$, $a_i<10$ | | $8,9$ | ^ | For all $0\le i<n$, $a_i<10^3$ | | $10,11$ | ^ | For all $0\le i<m$, $x_i,y_i<10$ | | $12,13$ | ^ | For all $0\le i<m$, $x_i,y_i<10^3$ | | $14\sim16$ | ^ | $A$ | | $17\sim19$ | ^ | For all $0\le i<m$, $r_i=n$ | | $20\sim22$ | $10^5$ | None | | $23\sim25$ | $2\times10^5$ | ^ |

Special property $A$: For all $0\le i<m$, after $l_i,r_i$ are given, $(x_i,y_i)$ are generated independently and uniformly at random from all ordered pairs of nodes that satisfy the limits.

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

Hint

Sample $1$ Explanation

• The tree corresponding to interval $[0,3)$ has $5$ nodes, and its Prüfer sequence is $[2,0,2]$. The edge set is $\{(1,2),(0,3),(0,2),(2,4)\}$. Therefore, nodes $0,2$ are adjacent.
• The tree corresponding to interval $[3,5)$ has $4$ nodes, and its Prüfer sequence is $[3,0]$. The edge set is $\{(1,3),(0,2),(0,3)\}$. Therefore, nodes $1,2$ are not adjacent.
• The tree corresponding to interval $[0,0)$ has $2$ nodes, and its Prüfer sequence is empty. The only edge is $(0,1)$. Therefore, nodes $0,1$ are adjacent.

Sample $2$

See kapok/kapok2.in and kapok/kapok2.ans in the contestants' directory.

This sample satisfies the constraints of test points $3\sim5$。

Sample $3$

See kapok/kapok3.in and kapok/kapok3.ans in the contestants' directory.

This sample satisfies the constraints of test points $3\sim5$。

Constraints

For all testdata:

• $1\le n,m\le2\times10^5$。
• For all $0\le i<n$, $0\le a_i<n+2$。
• For all $0\le i<m$, $0\le l_i\le r_i\le n$ and $0\le x_i,y_i<r_i-l_i+2$。

::cute-table{tuack} | Test point index | $n,m\le$ | Special property | |:-:|:-:|:-:| | $1,2$ | $500$ | None | | $3\sim5$ | $5000$ | ^ | | $6,7$ | $2\times10^5$ | For all $0\le i<n$, $a_i<10$ | | $8,9$ | ^ | For all $0\le i<n$, $a_i<10^3$ | | $10,11$ | ^ | For all $0\le i<m$, $x_i,y_i<10$ | | $12,13$ | ^ | For all $0\le i<m$, $x_i,y_i<10^3$ | | $14\sim16$ | ^ | $A$ | | $17\sim19$ | ^ | For all $0\le i<m$, $r_i=n$ | | $20\sim22$ | $10^5$ | None | | $23\sim25$ | $2\times10^5$ | ^ |

Special property $A$: For all $0\le i<m$, after $l_i,r_i$ are given, $(x_i,y_i)$ are generated independently and uniformly at random from all ordered pairs of nodes that satisfy the limits.

Hint

For an unrooted tree $T$ whose nodes are labeled $0\sim c-1$ ($c\ge2$):

• Perform $c-2$ operations in order, where the $i$-th operation ($0\le i<c-2$) is:
  • Find the current leaf with the smallest label $v_i$。
  • Record the label of its unique adjacent node $p_i$。
  • Then delete $v_i$ and its only incident edge from $T$。
• The resulting sequence of length $c-2$, $[p_0,p_1,\ldots,p_{c-3}]$, is the Prüfer sequence of $T$。

Translated by ChatGPT 5