题目描述：

给定一个整数数组 $arr$，您需要处理多个查询。每个查询包含一个区间 $[l, r]$，请您找出该区间内的最大值以及所有出现该最大值的下标序列。

输入：

• 第一行输入一个整数 $n$ $(1 \leq n \leq 100)$，表示数组的大小。
• 第二行输入 $n$ 个整数 $arr[i]$ $(1 \leq arr[i] \leq 10^6)$，表示数组的元素。
• 第三行输入一个整数 $q$ $(1 \leq q \leq 100)$，表示查询的次数。
• 接下来 $q$ 行，每行输入两个整数 $l$ 和 $r$ $(1 \leq l \leq r \leq n)$，表示查询的区间（注意：下标从 1 开始计数）。

输出：

对于每个查询，输出两行：

• 第一行输出区间内的最大值。
• 第二行输出所有最大值的下标（使用原数组的下标，从 1 开始计数），按升序排列，使用空格分隔。

示例：

输入：

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

输出：

7
3 5
7
3
7
3

提示：

• 如果最大值在查询区间内出现多次，输出所有下标。
• 由于数组下标从 1 开始，注意转换下标。

【循环4】最大值查询问题②

题解

题面分析

给定一个整数数组 arr，需要处理多个区间查询。每个查询给定一个区间 [l, r]，要求在该区间内找到最大值，并输出该最大值及其所有出现的下标（注意下标从1开始）。

思路

这道题是最大值查询的扩展版本，不仅需要找到区间内的最大值，还需要记录所有出现该最大值的下标。由于题目数据范围较小，采用简单的三重循环即可解决。

具体步骤如下：

1. 输入处理：

   • 读取数组长度 n 和数组元素。
   • 读取查询次数 q，然后依次处理每个查询。

2. 查询处理：

   • 对于每个查询，读取区间 [l, r]，并将其转换为0开始的索引。
   • 遍历区间 [l, r]，找到最大值 max_value 以及所有等于 max_value 的下标。
   • 输出 max_value 及其所有下标（1开始）。

3. 时间复杂度：

   • 三重循环，时间复杂度为O($q \times n$)，适用于数据范围较小的情况。

解释

1. 输入读取：

   • 使用 input() 和 map(int, input().split()) 读取输入。
   • n 为数组长度，arr 为数组元素列表。
   • q 为查询次数，之后依次读取每个查询的 [l, r]。

2. 查询处理：

   • 将输入的 [l, r] 转换为0开始的索引，以便于Python列表的索引操作。
   • 初始化 max_value 为区间的第一个元素，max_indices 为包含该元素下标的列表。
   • 遍历区间 [l, r]，更新 max_value 和 max_indices：
     • 如果当前元素大于 max_value，更新 max_value 并重置 max_indices。
     • 如果当前元素等于 max_value，将其下标加入 max_indices。

3. 结果输出：

   • 打印 max_value。
   • 使用 ' '.join(map(str, max_indices)) 将下标列表转换为字符串，并打印。

示例

输入

5
1 3 3 2 5
3
1 5
2 4
3 5

输出

5
5
3
2 3
5
5

解释

• 第一个查询 [1,5]：最大值为5，出现在下标5。
• 第二个查询 [2,4]：最大值为3，出现在下标2和3。
• 第三个查询 [3,5]：最大值为5，出现在下标5。

注意事项

• 下标转换：题目要求下标从1开始，而Python列表从0开始，因此在处理时需要进行转换。
• 输入处理：使用 input().split() 可以简化代码，适用于数据量较小的情况。如果数据量非常大，sys.stdin.readline() 会更高效，但根据题目要求，这里使用 input().split()。
• 输出格式：确保输出的下标之间用空格分隔，且每个查询的结果分别打印在不同的行。

这种方法适用于数据规模较小的情况。如果数据规模较大，可以考虑使用更高效的数据结构，如线段树或稀疏表（Sparse Table）来优化查询时间。

完整代码示例

以下是完整的代码，您可以直接运行并测试：

def main():
    # 读取输入
    n = int(input())
    arr = list(map(int, input().split()))
    
    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        l -= 1  # 转换为0开始的索引
        r -= 1
        
        max_value = arr[l]
        max_indices = [l + 1]  # 初始化下标列表（1开始）
        
        for i in range(l + 1, r + 1):
            if arr[i] > max_value:
                max_value = arr[i]
                max_indices = [i + 1]
            elif arr[i] == max_value:
                max_indices.append(i + 1)
        
        # 输出结果
        print(max_value)
        print(' '.join(map(str, max_indices)))

if __name__ == "__main__":
    main()