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

前言

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

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

Python 中的 bisect_left 和 bisect_right

1. bisect_left 函数

bisect_left 函数返回目标值不小于目标值的位置索引。简言之，它返回数组中第一个不小于指定值的元素的位置。如果指定值已经存在，返回该元素第一次出现的位置。

import bisect
arr = [1, 3, 3, 5, 7]
position = bisect.bisect_left(arr, 3)
print(position)  # 输出 1

2. bisect_right 函数

bisect_right 函数返回目标值大于目标值的位置索引。如果指定值已经存在，它返回该值最后一次出现后的下一个位置。

import bisect
arr = [1, 3, 3, 5, 7]
position = bisect.bisect_right(arr, 3)
print(position)  # 输出 3

主要区别

• bisect_left：查找目标值的第一个不小于目标值的位置。
• bisect_right：查找目标值的第一个大于目标值的位置。

题解

1. 输入与初始化

首先，我们需要输入数组的大小 n 和查询次数 Q，然后输入一个升序排列的数组。

# 输入数组的大小和查询次数
n, Q = map(int, input().split())

# 输入升序数组
arr = list(map(int, input().split()))

2. 查询每个元素的首次与最后一次出现位置

接下来，我们需要处理 Q 次查询。每次查询给定一个整数 x，要求找出其在数组中的首次和最后一次出现的位置。如果该元素不存在，则输出 -1 -1。

我们可以利用 bisect_left 和 bisect_right 来快速找到目标元素的位置。

2.1 查找首次出现的位置

使用 bisect_left 查找目标值 x 第一次出现的位置。bisect_left(arr, x) 返回第一个不小于 x 的位置。如果该位置的元素等于 x，则表示 x 存在于数组中，且返回的是首次出现的位置。

import bisect

# 输入查询的元素
x = int(input())

# 使用 bisect_left 查找第一个不小于 x 的位置
first = bisect.bisect_left(arr, x)

2.2 查找最后一次出现的位置

使用 bisect_right 查找目标值 x 最后一次出现后的下一个位置。bisect_right(arr, x) 返回第一个大于 x 的位置，减去 1 就是 x 的最后一次出现位置。

# 使用 bisect_right 查找第一个大于 x 的位置，减去1得到最后一次出现的位置
last = bisect.bisect_right(arr, x) - 1

2.3 判断目标值是否存在

如果通过 bisect_left 查找出来的位置不等于数组的长度，并且该位置上的元素等于 x，则说明 x 存在于数组中，且可以根据 bisect_left 和 bisect_right 的返回值分别得到首次和最后一次出现的位置。

如果 bisect_left 查找出来的位置超出了数组长度，或者该位置的元素不等于 x，则说明 x 不在数组中，我们应该返回 -1 -1。

# 如果first和last对应位置的元素等于x，则输出其首次和最后一次出现的位置
if first < len(arr) and arr[first] == x:
    print(first + 1, last + 1)  # 输出1-based的索引
else:
    print(-1, -1)  # 如果不存在，输出 -1 -1

3. 完整代码

下面是根据上面的思路写的完整代码：

import bisect

# 输入数组的大小和查询次数
n, Q = map(int, input().split())

# 输入升序数组
arr = list(map(int, input().split()))

# 处理每个查询
for _ in range(Q):
    # 输入查询的元素
    x = int(input())
    
    # 使用 bisect_left 查找第一个不小于 x 的位置
    first = bisect.bisect_left(arr, x)
    
    # 使用 bisect_right 查找第一个大于 x 的位置，减去1得到最后一次出现的位置
    last = bisect.bisect_right(arr, x) - 1
    
    # 如果first和last对应位置的元素等于x，则输出其首次和最后一次出现的位置
    if first < len(arr) and arr[first] == x:
        print(first + 1, last + 1)  # 输出1-based的索引
    else:
        print(-1, -1)  # 如果不存在，输出 -1 -1

题目描述：

给定一个升序排列的数组 $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$。