插入排序：位置追踪与修改

"插入排序是一种非常常见且简单的排序算法。小\u000AZ是一名大一的新生，今天H老师刚刚在上课的时候讲了插入排序算法。\n\n假设比较两个元素的时间为\u000A(1)O(1)，则插入排序可以以\u000A(n2)O(n2)的时间复杂度完成长度为\u000An的数组的排序。不妨假设这\u000An个数字分别存储在\u000A1,2,⋅⋅⋅,na1,a2,⋅⋅⋅,an之中，则如下伪代码给出了插入排序算法的一种最简单的实现方式：\n\n这下面是C/C++的示范代码:\n\nfor (int i = 1; i <= n; i++)\n\tfor (int j = i; j >= 2; j--)\n\t\tif (a[j] < a[j-1]) {\n\t\t\tint t = a[j-1];\n\t\t\ta[j-1] = a[j];\n\t\t\ta[j] = t;\n\t\t}\n这下面是Pascal的示范代码\n\nfor i:=1 to n do\n\tfor j:=i downto 2 do\n\t\tif a[j]<a[j-1] then\n\t\t\tbegin\n\t\t\t\tt:=a[i];\n\t\t\t\ta[i]:=a[j];\n\t\t\t\ta[j]:=t;\n\t\t\tend;\n为了帮助小\u000AZ更好的理解插入排序，小\u000AZ的老师H老师留下了这么一道家庭作业：\n\nH老师给了一个长度为\u000An的数组a，数组下标从1开始，并且数组中的所有元素均为非负整数。小\u000AZ需要支持在数组a上的Q次操作，操作共两种，参数分别如下：\n\n1\u000A1 x v：这是第一种操作，会将a的第x个元素，也就是ax的值，修改为v。保证1≤x≤n，1≤v≤109。注意这种操作会改变数组的元素，修改得到的数组会被保留，也会影响后续的操作。\n\n2\u000A2 x：这是第二种操作，假设H老师按照上面的伪代码对a数组进行排序，你需要告诉H老师原来a的第x个元素，也就是ax，在排序后的新数组所处的位置。保证1≤x≤n。注意这种操作不会改变数组的元素，排序后的数组不会被保留，也不会影响后续的操作。\n\nH老师不喜欢过多的修改，所以他保证类型1的操作次数不超过5000。\n\n小\u000AZ没有学过计算机竞赛，因此小\u000AZ并不会做这道题。他找到了你来帮助他解决这个问题。\n\n输入格式\n第一行，包含两个正整数n,Q，表示数组长度和操作次数。\n\n第二行，包含n个空格分隔的非负整数，其中第i个非负整数表示ai。\n\n接下来Q行，每行2∼3个正整数，表示一次操作，操作格式见【题目描述】。\n\n输出格式\n对于每一次类型为2的询问，输出一行一个正整数表示答案。\n内容：解题思路：\n根据题目给出的伪代码，实现插入排序，并在排序的过程中记录每个元素在原数组中的位置。\n具体步骤如下：\n\n1. 读取输入值n和Q，以及数组a的元素。\n\n2. 创建一个新数组sorted，用于存储排序后的数组。\n\n3. 对数组a进行插入排序，同时记录每个元素在原数组中的位置。\n\n4. 根据操作类型进行相应的处理：\n\t- 如果是类型1的操作，修改数组a中对应位置的元素的值。\n\t- 如果是类型2的操作，输出该元素在排序后的数组sorted中的位置。\n\n5. 重复步骤4，直到处理完所有操作。\n\nPython代码实现如下：\n\npython\nn, Q = map(int, input().split())\na = list(map(int, input().split()))\n\nsorted = sorted(a) # 对数组a进行排序\nindices = {} # 用于记录每个元素在原数组中的位置\n\nfor i in range(n):\n indices[sorted[i]] = i+1 # 记录每个元素在原数组中的位置\n\nfor _ in range(Q):\n op = list(map(int, input().split()))\n if op[0] == 1:\n a[op[1]-1] = op[2] # 修改数组a中对应位置的元素的值\n elif op[0] == 2:\n print(indices[a[op[1]-1]]) # 输出该元素在排序后的数组sorted中的位置\n\n\n时间复杂度分析：\n插入排序的时间复杂度为O(n^2)，每个操作的时间复杂度为O(1)，总时间复杂度为O(n^2 + Q)。由于n和Q的最大值均为10^5，因此该算法的时间复杂度是可接受的。\n