Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 5603 --2.插入排序(sort)
5603: 2.插入排序(sort)
警告!
题目
状态
题解(1)
题目描述
插入排序是一种非常常见且简单的排序算法。小 Z 是一名大一的新生,今天 H 老师刚刚在上课的时候讲了插入排序算法。 假设比较两个元素的时间为 $O(1)$,则插入排序可以以 $O(n^2)$ 的时间复杂度完成长度为 $n$ 的数组的排序。不妨假设这 $n$ 个数字分别存储在 $a_1, a_2, \ldots, a_n$ 之中,则如下伪代码给出了插入排序算法的一种最简单的实现方式: 这下面是 C/C++ 的示范代码 ```cpp 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 的示范代码 ```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; ``` 为了帮助小 Z 更好的理解插入排序,小 Z 的老师 H 老师留下了这么一道家庭作业: H 老师给了一个长度为 $n$ 的数组 $a$,数组下标从 $1$ 开始,并且数组中的所有元素均为非负整数。小 Z 需要支持在数组 $a$ 上的 $Q$ 次操作,操作共两种,参数分别如下: $1~x~v$:这是第一种操作,会将 $a$ 的第 $x$ 个元素,也就是 $a_x$ 的值,修改为 $v$。保证 $1 \le x \le n$,$1 \le v \le 10^9$。**注意这种操作会改变数组的元素,修改得到的数组会被保留,也会影响后续的操作**。 $2~x$:这是第二种操作,假设 H 老师按照**上面的伪代码**对 $a$ 数组进行排序,你需要告诉 H 老师原来 $a$ 的第 $x$ 个元素,也就是 $a_x$,在排序后的新数组所处的位置。保证 $1 \le x \le n$。**注意这种操作不会改变数组的元素,排序后的数组不会被保留,也不会影响后续的操作**。 H 老师不喜欢过多的修改,所以他保证类型 $1$ 的操作次数不超过 $5000$。 小 Z 没有学过计算机竞赛,因此小 Z 并不会做这道题。他找到了你来帮助他解决这个问题。
输入
输入的第一行包含两个正整数 $n, Q$,表示数组长度和操作次数。保证 $1 \le n \le 8,000$,$1 \le Q \le 2 \times {10}^5$。 输入的第二行包含 $n$ 个空格分隔的非负整数,其中第 $i$ 个非负整数表示 $a_i$。保证 $1 \le a_i \le {10}^9$。 接下来 $Q$ 行,每行 $2 \sim 3$ 个正整数,表示一次操作,操作格式见题目描述。
输出
对于每一次类型为 $2$ 的询问,输出一行一个正整数表示答案。
样例输入输出
输入#1
复制
3 4 3 2 1 2 3 1 3 2 2 2 2 3
输出#1
复制
1 1 2
提示
**【样例解释 #1】** 在修改操作之前,假设 H 老师进行了一次插入排序,则原序列的三个元素在排序结束后所处的位置分别是 $3, 2, 1$。 在修改操作之前,假设 H 老师进行了一次插入排序,则原序列的三个元素在排序结束后所处的位置分别是 $3, 1, 2$。 注意虽然此时 $a_2 = a_3$,但是我们**不能将其视为相同的元素**。 **【样例 #2】** 见附件中的 `sort/sort2.in` 与 `sort/sort2.ans`。 该测试点数据范围同测试点 $1 \sim 2$。 **【样例 #3】** 见附件中的 `sort/sort3.in` 与 `sort/sort3.ans`。 该测试点数据范围同测试点 $3 \sim 7$。 **【样例 #4】** 见附件中的 `sort/sort4.in` 与 `sort/sort4.ans`。 该测试点数据范围同测试点 $12 \sim 14$。 **【数据范围】** 对于所有测试数据,满足 $1 \le n \le 8,000$,$1 \le Q \le 2 \times 10^5$,$1 \le x \le n$,$1 \le v,a_i \le 10^9$。 对于所有测试数据,保证在所有 $Q$ 次操作中,至多有 $5000$ 次操作属于类型一。 各测试点的附加限制及分值如下表所示。 | 测试点 | $n$ | $Q$ | 特殊性质 | |:-----------: | :-----------: | :-----------: | :-----------: | | $1,2,3,4$ | $\le 10$ | $\le 10$ | 无 | | $5,6,7,8,9$ | $\le 300$ | $\le 300$ | 无 | | $10,11,12,13$ | $\le 1,500$ | $\le 1,500$ | 无 | | $14,15,16$ | $\le 8,000$ | $\le 8,000$| 保证所有输入的 $a_i,v$ 互不相同 | | $17,18,19$ | $\le 8,000$ | $\le 8,000$ | 无 | | $20,21,22$ | $\le 8,000$ | $\le 2\times 10^5$ | 保证所有输入的 $a_i,v$ 互不相同 | | $23,24,25$ | $\le 8,000$ | $\le 2\times 10^5$ | 无 |
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
未评定
标签
点击显示
if ($pr_flag) { ?>
递交数
84
已通过
19
} ;?>
通过率
23%
时间限制
1 秒
内存限制
512 MB
来源
2021CSP J2
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和