← 返回题目列表

Codeforces · 2106/E

E. 狼

中文机器翻译题面 查看原题

Wolf 找到了 $$$n$$$ 羊,其美味值为 $$$p_1, p_2, ..., p_n$$$,其中 $$$p$$$ 是排列 $$$^{\text{*}}$$$。 Wolf想对$$$p$$$进行二分查找,找到味道为$$$k$$$的羊,但$$$p$$$不一定是排序的。在 $$$[l, r]$$$ 范围内对 $$$k$$$ 成功进行二分查找表示为 $$$f(l, r, k)$$$,其定义如下:

如果 $$$l \gt r$$$,则 $$$f(l, r, k)$$$ 失败。否则,设 $$$m = \lfloor\frac{l + r}{2}\rfloor$$$,并且:

  • 如果 $$$p_m = k$$$,则 $$$f(l, r, k)$$$ 为 成功,
  • 如果 $$$p_m \lt k$$$,则 $$$f(l, r, k) = f(m+1, r, k)$$$,
  • 如果 $$$p_m \gt k$$$,则 $$$f(l, r, k) = f(l, m-1, k)$$$。

书呆子牛决定帮助狼。 Cow the Nerd 被给予 $$$q$$$ 查询,每个查询由三个整数 $$$l$$$、$$$r$$$ 和 $$$k$$$ 组成。在搜索开始之前,Cow the Nerd 可以选择一个非负整数 $$$d$$$ 和 $$$d$$$ 索引 $$$1 \le i_1 \lt i_2 \lt \ldots \lt i_d \le n$$$,其中 $$$p_{i_j} \neq k$$$ 在所有 $$$1 \leq j \leq d$$$ 上。然后,他可以按照自己的喜好对元素 $$$p_{i_1}, p_{i_2}, ..., p_{i_d}$$$ 重新排序。

对于每个查询,输出 最小值 书呆子 Cow 必须选择的整数 $$$d$$$,以便 $$$f(l, r, k)$$$ 可以 成功,或报告这是不可能的。请注意,查询是独立的,并且实际上并未执行重新排序。

$$$^{\text{*}}$$$长度 $$$n$$$ 的排列是一个数组,其中包含从 $$$1$$$ 到 $$$n$$$ 的每个整数恰好一次。

输入

输入的第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^4)$$$ — 测试用例的数量。

每个测试的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ $$$(1 \le n, q \le 2 \cdot 10^5)$$$ - 分别是 $$$p$$$ 的长度和查询数量。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2, ..., p_n$$$ — 第 $$$i$$$ 只羊的美味程度。保证从 $$$1$$$ 到 $$$n$$$ 的每个整数在 $$$p$$$ 中恰好出现一次。

以下 $$$q$$$ 行包含三个整数 $$$l$$$、$$$r$$$ 和 $$$k$$$ $$$(1 \le l \le r \le n, 1 \le k \le n)$$$ — 将执行二分搜索的范围以及每个查询搜索的整数。

保证所有情况下 $$$n$$$ 的总和与 $$$q$$$ 的总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个查询,输出 Cow the Nerd 必须选择的最小整数 $$$d$$$,以便 $$$f(l, r, k)$$$ 在新行上成功。如果不可能,则输出$$$-1$$$。

示例

输入
复制

8
5 3
1 2 3 4 5
1 5 4
1 3 4
3 4 4
7 4
3 1 5 2 7 6 4
3 4 2
2 3 5
1 5 6
1 7 3
2 1
2 1
1 2 1
1 1
1
1 1 1
7 1
3 4 2 5 7 1 6
1 7 1
16 1
16 10 12 6 13 9 14 3 8 11 15 2 7 1 5 4
1 16 4
16 1
14 1 3 15 4 5 6 16 7 8 9 10 11 12 13 2
1 16 14
13 1
12 13 10 9 8 4 11 5 7 6 2 1 3
1 13 2

输出
复制

0 -1 0 
2 0 -1 4 
-1 
0 
-1 
-1 
-1 
-1 

注意

在第一个例子中,第二个查询:由于$$$4$$$在前三个元素中不存在,因此在该范围内搜索时不可能找到它。

在第二个示例中,在第一个查询中,您可以选择索引 $$$2$$$、$$$3$$$,并将它们交换为 $$$p = [3, 5, 1, 2, 7, 6, 4]$$$。然后,$$$f(3, 4, 2)$$$ 将按如下方式工作:

  1. 令 $$$m = \lfloor \frac{3 + 4}{2} \rfloor = 3$$$。因为 $$$p_3 = 1 \lt 2$$$,所以 $$$f(3, 4, 2) = f(4, 4, 2)$$$。
  2. 令 $$$m = \lfloor \frac{4 + 4}{2} \rfloor = 4$$$。因为 $$$p_4 = 2 = k$$$,所以 $$$f(4, 4, 2)$$$ 成功。因此,$$$f(3, 4, 2)$$$ 也是成功的。

选择的总指数为$$$2$$$,因此最终成本为$$$2$$$,可以看出这是最小的。请注意,对于此查询,我们无法选择索引 $$$4$$$,因为 $$$p_4 = k = 2$$$。

在第二个示例的最后一个查询中,我们可以选择索引 $$$2, 3, 4, 5$$$ 并重新排列它们,使 $$$p = [3, 5, 2, 7, 1, 6, 4]$$$。那么,$$$f(1, 7, 3)$$$ 就成功了。