2021 CSP-J 第二轮 T2｜插入排序

一、完整题目

题目描述

插入排序是一种常见且简单的排序算法。假设比较两个元素的时间为 O(1)，插入排序可以在 O(n^2) 时间内完成长度为 n 的数组排序。题面给出的 C/C++ 示意代码如下：

for (int i = 1; i <= n; i++)
    for (int j = i; j >= 2; j--)
        if (a[j] < a[j - 1]) {
            int t = a[j - 1];
            a[j - 1] = a[j];
            a[j] = t;
        }

题面同时给出的 Pascal 示意代码如下：

for i:=1 to n do
    for j:=i downto 2 do
        if a[j]<a[j-1] then
            begin
                t:=a[i];
                a[i]:=a[j];
                a[j]:=t;
            end;

H 老师给出一个长度为 n 的数组 a，下标从 1 开始，数组中的所有元素均为非负整数。需要支持 Q 次操作：

• 1 x v：把 a_x 修改为 v。修改后的数组会被保留，并影响后续操作；
• 2 x：假设按题面给出的插入排序代码对当前数组进行排序，询问原来第 x 个元素 a_x 在排序后的新数组中所处的位置。这次假想排序不会被保留，也不会影响后续操作。

类型 1 的操作次数不超过 5000。

输入格式

从文件 sort.in 中读入数据。

第一行包含两个正整数 n,Q，表示数组长度和操作次数。

第二行包含 n 个空格分隔的非负整数，第 i 个数表示 a_i。

接下来 Q 行，每行 2～3 个正整数，表示一次操作，格式见题目描述。

输出格式

输出到文件 sort.out 中。

对于每一次类型为 2 的询问，输出一行一个正整数表示答案。

样例 1

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

1
1
2

初始数组为 [3,2,1]，稳定排序后的原下标顺序是 [3,2,1]，所以原下标 3 的位置为 1。把 a_3 修改为 2 后，数组变为 [3,2,2]。相等元素不会交换，排序后的原下标顺序是 [2,3,1]，因此原下标 2、3 的位置分别为 1、2。

附加样例

• 样例 2：见 sort/sort2.in 与 sort/sort2.ans，范围同测试点 1～2；
• 样例 3：见 sort/sort3.in 与 sort/sort3.ans，范围同测试点 3～7；
• 样例 4：见 sort/sort4.in 与 sort/sort4.ans，范围同测试点 12～14。

数据范围与测试点

对于所有数据，1≤n≤8000，1≤Q≤2×10^5，1≤x≤n，1≤v,a_i≤10^9，并且类型 1 操作不超过 5000 次。