题解 | #【模板】二分#（Python3）

def lower_bound(arr, l, r, x):
    """在数组 arr 的区间 [l, r) 中找到第一个大于等于 x 的元素的索引"""
    while l < r:
        mid = (l + r) // 2
        if arr[mid] < x:
            l = mid + 1
        else:
            r = mid
    return l

def upper_bound(arr, l, r, x):
    """在数组 a 的区间 [l, r) 中找到第一个大于 x 的元素的索引"""
    while l < r:
        mid = (l + r) // 2
        if arr[mid] <= x:
            l = mid + 1
        else:
            r = mid
    return l

def find_y(arr, op, l, r, x):
    """根据给出的option找到对应的y值"""
    # 最小的 y 使得 x≤y 的指针为 lower_bound 。
    if op == 1:
        idx = lower_bound(arr, l, r, x)
        return arr[idx] if idx < r and arr[idx] >= x else -1
    # 最小的 y 使得 x<y 的指针为 upper_bound 。
    elif op == 2:
        idx = upper_bound(arr, l, r, x)
        return arr[idx] if idx < r else -1
    # 最大的 y 使得 y<x 的指针为 lower_bound−1 。
    elif op == 3:
        idx = lower_bound(arr, l, r, x)
        return arr[idx - 1] if idx > l else -1
    # 最大的 y 使得 y≤x 的指针为 upper_bound−1 。
    elif op == 4:
        idx = upper_bound(arr, l, r, x)
        return arr[idx - 1] if idx > l and arr[idx - 1] <= x else -1

for _ in range(0,m):
    op, left, right, x = map(int, input().split())
    y = find_y(a, op, left, right, x)
    print(y)

lower_bound 和 upper_bound 函数是二分查找算法的两种变体，它们在有序数组中查找特定元素的索引。下面我将解释这两个函数中的 if 条件是如何工作的：

lower_bound 函数

lower_bound 函数用于找到第一个大于等于给定值 x 的元素的索引。

• if arr[mid] < x:：检查中间元素是否小于 x。如果是，则说明第一个大于等于 x 的元素在 mid 右侧（因为数组是有序的），所以我们更新左边界 l 为 mid + 1。
• else:：如果中间元素不小于 x，那么 mid 可能就是我们要找的元素，或者第一个大于等于 x 的元素在 mid 的左侧。因此，我们将右边界 r 更新为 mid。

通过这种方式，我们不断缩小搜索范围，直到找到第一个大于等于 x 的元素。

upper_bound 函数

upper_bound 函数用于找到第一个大于给定值 x 的元素的索引。

• if arr[mid] <= x:：检查中间元素是否小于等于 x。如果是，则说明第一个大于 x 的元素在 mid 右侧，所以我们更新左边界 l 为 mid + 1。
• else:：如果中间元素大于 x，那么 mid 可能就是我们要找的元素，或者第一个大于 x 的元素在 mid 的左侧。因此，我们将右边界 r 更新为 mid。

同样，我们通过这种方式不断缩小搜索范围，直到找到第一个大于 x 的元素。

总的来说，这两个函数的关键在于如何根据中间元素与目标值 x 的比较结果来调整搜索范围。lower_bound 在找到大于等于 x 的元素时停止，而 upper_bound 在找到大于 x 的元素时停止。这两个函数都返回左边界 l，在二分查找结束时，l 就是我们要找的元素的索引（如果存在的话）。

操作 1 (op == 1)

• idx = lower_bound(arr, l, r, x): 使用 lower_bound 函数找到第一个大于等于 x 的元素的索引。
• return arr[idx] if idx < r and arr[idx] >= x else -1: 如果找到的索引 idx 在区间 [l, r) 内，并且对应的元素大于等于 x，则返回该元素。否则，返回 -1。

操作 2 (op == 2)

• idx = upper_bound(arr, l, r, x): 使用 upper_bound 函数找到第一个大于 x 的元素的索引。
• return arr[idx] if idx < r else -1: 如果找到的索引 idx 在区间 [l, r) 内，则返回该元素。否则，返回 -1。

操作 3 (op == 3)

• idx = lower_bound(arr, l, r, x): 使用 lower_bound 函数找到第一个大于等于 x 的元素的索引。
• return arr[idx - 1] if idx > l else -1: 如果找到的索引 idx 大于 l，则返回索引 idx - 1 对应的元素。这是因为我们要找的是小于 x 的最大元素。如果 idx 等于 l，则说明没有找到小于 x 的元素，返回 -1。

操作 4 (op == 4)

• idx = upper_bound(arr, l, r, x): 使用 upper_bound 函数找到第一个大于 x 的元素的索引。
• return arr[idx - 1] if idx > l and arr[idx - 1] <= x else -1: 如果找到的索引 idx 大于 l，并且索引 idx - 1 对应的元素小于等于 x，则返回该元素。否则，返回 -1。

在每种操作中，我们都在寻找特定的元素，并使用 lower_bound 或 upper_bound 函数来确定该元素的索引。根据操作的不同，我们可能返回找到的元素，或者返回 -1（如果没有找到符合条件的元素）。

n, m = map(int,input().split())
a = list(map(int, input().split()))
def lower_bound(l, r, x):
    """在数组 arr 的区间 [l, r) 中找到第一个大于等于 x 的元素的索引"""
    while l < r:
        mid = (l + r) // 2
        if a[mid] < x:
            l = mid + 1
        else:
            r = mid
    return l

def upper_bound(l, r, x):
    """在数组 a 的区间 [l, r) 中找到第一个大于 x 的元素的索引"""
    while l < r:
        mid = (l + r) // 2
        if a[mid] <= x:
            l = mid + 1
        else:
            r = mid
    return l

for _ in range(0,m):
    op, left, right, x = map(int, input().split())
    # 最小的 y 使得 x≤y 的指针为 lower_bound 。
    if(op==1):
        idx = lower_bound(left,right,x)
        if(idx==right):
            print(-1)
        else:
            print(a[idx])
    # 最小的 y 使得 x<y 的指针为 upper_bound 。
    elif(op==2):
        idx = upper_bound(left,right,x)
        if(idx==right):
            print(-1)
        else:
            print(a[idx])
    # 最大的 y 使得 y<x 的指针为 lower_bound−1 。
    elif(op==3):
        idx = lower_bound(left,right,x)
        if(idx==left):
            print(-1)
        else:
            print(a[idx-1])
    # 最大的 y 使得 y≤x 的指针为 upper_bound−1 。
    else:
        idx = upper_bound(left,right,x)
        if(idx==left):
            print(-1)
        else:
            print(a[idx-1])