[AdditionalFile5367.zip](file://AdditionalFile5367.zip?type=additional_file)

#5367. 「OOI 2024 Day 2」伯伦卡与 Pether

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

题目描述

题目译自 Open Olympiad in Informatics 2024 Day2 T3 「Три массива / Three Arrays」。

有一天，伯利兰国的公主伯伦卡决定给她的熟人 ReLu 一个惊喜。知道 ReLu 和她一样对加密货币感兴趣，伯伦卡决定创建自己的区块链加密货币 Pether。

在参加了一系列由网络安全个人成长专家教练提供的课程和培训后，伯伦卡决定 Pether 必须得到最佳保护。因此，由于极其复杂和混乱的限制，并非所有用户都可以相互交换 Pether。

Pether 区块链货币的系统确实复杂而混乱。所有用户编号为从 $1$ 到 $n$ 的整数。每个用户被分配一个唯一的标识符 $a_{i}$。此外，货币还固定了一个安全参数 $d$。

用户 $i$ 只能直接将货币转账给用户 $j$，如果满足 $i < j$ 且 $a_i < a_j$。但这还不够！直接转账是通过一系列中间用户进行一系列交易完成的。在每次交易过程中，每个后续中间用户（包括最终用户 $j$）的编号必须递增，但增量不得超过 $d$。此外，除 $i$ 和 $j$ 外的所有中间用户的标识符必须严格小于 $a_i$。

更正式地说，用户 $i$ 可以直接将加密货币转账给用户 $j$，如果满足以下条件：

1. $i < j$
2. $a_{i} < a_{j}$
3. 存在一个长度为 $k$ 的中间用户序列 $x$，使得：
   • $i = x_1 < x_2 < \ldots < x_{k-1} < x_{k} = j$
   • 对于所有 $1 \le t \le k - 1$，$x_{t + 1} - x_{t} \le d$
   • 对于所有 $2 \le t \le k - 1$，$a_{x_t} < a_{i}$

伯伦卡请你——她的程序员熟人——帮助解析这个系统，并为一些用户对确定他们如何相互传递 Pether。

你需要回答 $q$ 个查询。在每个查询中，你需要确定是否存在一个直接转账序列（可能通过中间用户），使得从用户 $u_i$ 到用户 $v_i$ 可以传递 Pether。在某些查询中，还需要最小化从 $u_i$ 到 $v_i$ 传递货币所需的直接转账次数。注意，在每次直接转账中不需要最小化交易次数。

输入格式

第一行包含三个整数 $n, d, g$ $(1 \leq n, d \leq 300000, 0 \leq g \leq 12)$，分别表示用户数量、安全参数和子任务编号。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_{i} \leq n)$，表示用户的标识符。保证所有 $a_i$ 互不相同。

第三行包含一个整数 $q$ $(1 \leq q \leq 300000)$，表示查询数量。

接下来的 $q$ 行，每行包含三个整数 $t_{i}, u_{i}, v_{i}$ $(t_{i} \in \{1, 2\}, 1 \leq u_{i} < v_{i} \leq n)$，其中 $u_i$ 是需要发送货币的用户，$v_i$ 是需要接收货币的用户。如果 $t_i = 1$，则需要确定是否可以传递货币；如果 $t_i = 2$，则需要额外最小化直接转账次数。

输出格式

输出 $q$ 行，第 $i$ 行是第 $i$ 个查询的答案。

如果无法从用户 $u_i$ 传递货币到用户 $v_i$，则对第 $i$ 个查询输出 $0$。否则，如果 $t_i = 1$，输出 $1$；如果 $t_i = 2$，输出从 $u_i$ 到 $v_i$ 传递 Pether 所需的最小直接转账次数。

样例 1

输入

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

输出

1
0
1
3
4
1

在第一个样例中，可能的直接转账如下：

• 第一个查询：编号为 $1$ 的用户可以直接转账给编号为 $3$ 的用户，通过中间用户 $2$ 进行 $2$ 次交易。
• 第二个查询：编号为 $1$ 和 $2$ 的用户之间无法直接转账，因为 $a_{1} = 2 > a_{2} = 1$。
• 第三个查询：可以从编号为 $1$ 的用户传递货币到编号为 $4$ 的用户，通过两个直接转账：先从 $1$ 到 $3$，再从 $3$ 到 $4$。由于 $t_3 = 1$，仅需确认传递可能性，因此答案为 $1$。
• 第四个查询：可以通过三个直接转账完成：从 $1$ 到 $3$，从 $3$ 到 $4$，从 $4$ 到 $5$。

样例 2

输入

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

输出

2
2
3
2
2
1

在第二个样例中，可能的直接转账如下：

样例 3

输入

10 2 0
2 1 4 3 5 6 8 7 10 9
10
2 1 5
1 2 5
2 3 5
2 1 9
2 5 8
2 3 9
2 1 8
1 1 2
2 3 8
2 1 9

输出

2
1
1
4
2
3
3
0
2
4

在第三个样例中，可能的直接转账如下：

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。