【二分3】找前驱后继问题

前言

在本题中，我们需要在一个升序排列的数组中多次查询某个元素的首次出现和最后一次出现的位置。如果目标元素存在，我们需要返回它在数组中首次和最后一次出现的位置。如果不存在该元素，则返回 -1 -1。这种问题可以通过二分查找来高效解决。

Python 提供了 bisect 模块，它包含了类似 C++ 中 lower_bound 和 upper_bound 函数的功能。我们可以通过 bisect_left 和 bisect_right 来解决本题。

Python 中的 bisect_left 和 bisect_right

题目描述：

给定一个升序排列的数组 $A$ 和 $Q$ 次询问。对于每次询问，您需要找到指定元素 $x$ 在数组中第一次和最后一次出现的位置。如果该元素不存在于数组中，则返回 $(-1, -1)$。

输入格式：

• 第一行包含两个整数 $n$ 和 $Q$，分别表示数组的长度和询问的次数。

• 第二行包含 $n$ 个整数，表示数组 $A$ 的元素，$A[i]$ ($1 \leq i \leq n$) 保证为升序排列。

• 接下来的 $Q$ 行，每行包含一个整数 $x$，表示您要查询的元素。

  $1 \leq n \leq 100000$

  $1 \leq Q \leq 10000$

输出格式：

对于每次询问，输出一行，包含两个整数，分别表示元素 $x$ 在数组中的第一次和最后一次出现的位置。如果该元素不存在，输出 $-1 -1$。

示例：

输入：

7 3
1 2 2 3 4 4 5
2
4
6

输出：

2 3
5 6
-1 -1

说明：

• 对于询问 $2$，元素 $2$ 在数组中第一次出现的位置是 $2$，最后一次出现的位置是 $3$。
• 对于询问 $4$，元素 $4$ 在数组中第一次出现的位置是 $5$，最后一次出现的位置是 $6$。
• 对于询问 $6$，元素 $6$ 不存在于数组中，因此输出 $-1 -1$。