题目描述插入排序是一种非常常见且简单的排序算法。小 �Z 是一名大一的新生今天 H 老师刚刚在上课的时候讲了插入排序算法。假设比较两个元素的时间为 �1O1 则插入排序可以以 ��2On 2 的时间复杂度完成长度为 �n 的数组的排序。不妨假设这 �n 个数字分别存储在 �1�2⋅⋅⋅��a 1 a 2 ⋅⋅⋅a n 之中则如下伪代码给出了插入排序算法的一种最简单的实现方式：这下面是 C

解题思路： 根据题目给出的伪代码，实现插入排序，并在排序的过程中记录每个元素在原数组中的位置。 具体步骤如下：

1. 读取输入值n和Q，以及数组a的元素。

2. 创建一个新数组sorted，用于存储排序后的数组。

3. 对数组a进行插入排序，同时记录每个元素在原数组中的位置。

4. 根据操作类型进行相应的处理：

   • 如果是类型1的操作，修改数组a中对应位置的元素的值。

   • 如果是类型2的操作，输出该元素在排序后的数组sorted中的位置。

5. 重复步骤4，直到处理完所有操作。

Python代码实现如下：

n, Q = map(int, input().split())
a = list(map(int, input().split()))

sorted = sorted(a)  # 对数组a进行排序
indices = {}  # 用于记录每个元素在原数组中的位置

for i in range(n):
    indices[sorted[i]] = i+1  # 记录每个元素在原数组中的位置

for _ in range(Q):
    op = list(map(int, input().split()))
    if op[0] == 1:
        a[op[1]-1] = op[2]  # 修改数组a中对应位置的元素的值
    elif op[0] == 2:
        print(indices[a[op[1]-1]])  # 输出该元素在排序后的数组sorted中的位置

时间复杂度分析： 插入排序的时间复杂度为O(n^2)，每个操作的时间复杂度为O(1)，总时间复杂度为O(n^2 + Q)。由于n和Q的最大值均为10^5，因此该算法的时间复杂度是可接受的