【题解】[CSP-J 2021] 插入排序
[CSP-J 2021] 插入排序
题目描述
插入排序是一种非常常见且简单的排序算法。小 Z 是一名大一的新生，今天 H 老师刚刚在上课的时候讲了插入排序算法。
假设比较两个元素的时间为 O(1)\mathcal O(1)O(1)，则插入排序可以以 O(n2)\mathcal O(n^2)O(n2) 的时间复杂度完成长度为 nnn 的数组的排序。不妨假设这 nnn 个数字分别存储在 a1,a2,…,ana_1, a_2, \ldots, a_na1,a2,…,an 之中，则如下伪代码给出了插入排序算法的一种最简单的实现方式：
这下面是 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;为了帮助小 Z 更好的理解插入排序，小 Z 的老师 H 老师留下了这么一道家庭作业：
H 老师给了一个长度为 nnn 的数组 aaa，数组下标从 111 开始，并且数组中的所有元素均为非负整数。小 Z 需要支持在数组 aaa 上的 QQQ 次操作，操作共两种，参数分别如下：
1 x v1~x~v1 x v：这是第一种操作，会将 aaa 的第 xxx 个元素，也就是 axa_xax 的值，修改为 vvv。保证 1≤x≤n1 \le x \le n1≤x≤n，1≤v≤1091 \le v \le 10^91≤v≤109。注意这种操作会改变数组的元素，修改得到的数组会被保留，也会影响后续的操作。
2 x2~x2 x：这是第二种操作，假设 H 老师按照上面的伪代码对 aaa 数组进行排序，你需要告诉 H 老师原来 aaa 的第 xxx 个元素，也就是 axa_xax，在排序后的新数组所处的位置。保证 1≤x≤n1 \le x \le n1≤x≤n。注意这种操作不会改变数组的元素，排序后的数组不会被保留，也不会影响后续的操作。
H 老师不喜欢过多的修改，所以他保证类型 111 的操作次数不超过 500050005000。
小 Z 没有学过计算机竞赛，因此小 Z 并不会做这道题。他找到了你来帮助他解决这个问题。
输入格式
第一行，包含两个正整数 n,Qn, Qn,Q，表示数组长度和操作次数。
第二行，包含 nnn 个空格分隔的非负整数，其中第 iii 个非负整数表示 aia_iai。
接下来 QQQ 行，每行 2∼32 \sim 32∼3 个正整数，表示一次操作，操作格式见【题目描述】。
输出格式
对于每一次类型为 222 的询问，输出一行一个正整数表示答案。
样例 #1
样例输入 #1
3 4
3 2 1
2 3
1 3 2
2 2
2 3样例输出 #1
1
1
2提示
【样例解释 #1】
在修改操作之前，假设 H 老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是 3,2,13, 2, 13,2,1。
在修改操作之后，假设 H 老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是 3,1,23, 1, 23,1,2。
注意虽然此时 a2=a3a_2 = a_3a2=a3，但是我们不能将其视为相同的元素。
【样例 #2】
见附件中的 sort/sort2.in 与 sort/sort2.ans。
该测试点数据范围同测试点 1∼21 \sim 21∼2。
【样例 #3】
见附件中的 sort/sort3.in 与 sort/sort3.ans。
该测试点数据范围同测试点 3∼73 \sim 73∼7。
【样例 #4】
见附件中的 sort/sort4.in 与 sort/sort4.ans。
该测试点数据范围同测试点 12∼1412 \sim 1412∼14。
【数据范围】
对于所有测试数据，满足 1≤n≤80001 \le n \le 80001≤n≤8000，1≤Q≤2×1051 \le Q \le 2 \times {10}^51≤Q≤2×105，1≤x≤n1 \le x \le n1≤x≤n，1≤v,ai≤1091 \le v,a_i \le 10^91≤v,ai≤109。
对于所有测试数据，保证在所有 QQQ 次操作中，至多有 500050005000 次操作属于类型一。
各测试点的附加限制及分值如下表所示。
测试点 | n≤n \len≤ | Q≤Q \leQ≤ | 特殊性质 |
|---|---|---|---|
1∼41 \sim 41∼4 | 101010 | 101010 | 无 |
5∼95 \sim 95∼9 | 300300300 | 300300300 | 无 |
10∼1310 \sim 1310∼13 | 150015001500 | 150015001500 | 无 |
14∼1614 \sim 1614∼16 | 800080008000 | 800080008000 | 保证所有输入的 ai,va_i,vai,v 互不相同 |
17∼1917 \sim 1917∼19 | 800080008000 | 800080008000 | 无 |
20∼2220 \sim 2220∼22 | 800080008000 | 2×1052 \times 10^52×105 | 保证所有输入的 ai,va_i,vai,v 互不相同 |
23∼2523 \sim 2523∼25 | 800080008000 | 2×1052 \times 10^52×105 | 无 |
分析
阅读题面，可知题目要我们输出的是原来aaa 的第xxx个元素，也就是axa_xax ，在排序后的新数组所处的位置。
题目中除了查询操作以外还有一个操作为修改操作：将 aaa 的第 xxx 个元素，也就是 axa_xax 的值，修改为 vvv。
其中，修改操作会改变原数组的内容，且修改的是原数列位置上的内容，并修改内容会被保留下来。意味着元素修改可能就会影响数列的排序。
暴力思路
保留原序列aaa，开一个数组bbb，每次修改在原序列aaa上进行修改；查询时，则将aaa中存储到bbb中，对数列bbb
进行排序，再输出axa_xax在排序后的位置即可。
注意相同值但不同位置元素不能视为相同的元素，所以排序时要注意保持原序列相同元素值的相对位置。
bool cmp(node x,node y){
if(x.v!=y.v) return x.v<y.v;
return x.id<y.id;
}分析下复杂度为O(Qnlogn)O(Qnlogn)O(Qnlogn)。此时数据范围最大n≤8000，Q≤2×105n \le8000，Q\leq 2\times10^5n≤8000，Q≤2×105 ，会超时。得到52分。
优化1.0
思考程序中哪块耗时较多？可发现是在查询时，每次都需要O(nlogn)O(nlogn)O(nlogn)的复杂度进行排序，这块用时较长。在这思考如何优化该过程。我们的目的是找到axa_xax的位置即可，实际上不需要你去将其他元素排序好，此时只需盯着axa_xax即可，统计在整个序列中排在它前面的元素有几个，就能知道它在第几个位置了。
scanf("%d",&x);
int cnt=0;
for(int j=1;j<=n;j++){
if(cmp(a[j],a[x])){
cnt++;
}
}
printf("%d\n",cnt+1);分析下复杂度为O(Qn)O(Qn)O(Qn)。比之前的小，但是还是会超时。得到76分。
优化2.0
此时再仔细分析下，注意题目中的数据范围“对于所有测试数据，保证在所有 QQQ 次操作中，至多有 500050005000 次操作属于类型一。”操作类型一为修改操作，类型二维查询操作。之前每次都是O(n)O(n)O(n)的复杂度确定元素位置，O(1)O(1)O(1)的复杂度进行修改。查询的操作比较多，若能再次降低查询时的复杂度，就能优化整体的时间了。
可发现，修改操作远少于查询的操作，若针对一个有序的数列查找原来元素的当前位置关系，这是可以较方便的构建映射关系的。
//site[x]:原序列a[x]在排好后的位置
for(int i=1;i<=n;i++){
site[a[i].id]=i;
}我们在执行完操作一，修改完原序列中的元素值之后，再把序列排序下，然后再重新构建位置关系。把用时长的执行的次数少些。
此时还是只有76，因为对于n来说范围也是达到了800080008000的500050005000操作一依然会超。因为排序用时为O(nlogn)O(nlogn)O(nlogn) 。
优化3.0
实际可发现，我们每次修改只更改了一个元素的值，也就是说，剩余元素在整体上是有序的，对于大部分都是有序的数据可以使用插入排序进行优化。我们可以将修改后的元素，插入到n−1n-1n−1个有序元素中。排序复杂度就能降为O(n)O(n)O(n)，这样就能满足要求了。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,q;
struct node{
int id,val;
}a[8005];
int site[8005];//site[x] 原数列的第x个元素的当前位置
/*
3 2 1
2 3 => 1
1 3 2 =>3 2 2
2 2 1
2 3 2
*/
bool cmp(node x,node y){
return x.val!=y.val?x.val<y.val:x.id<y.id;
}
//修改
void upd(int x,int v){
a[site[x]].val=v;//修改原数列中的值
node key=a[site[x]];
//往前挪删除原序列a[x] ，使得剩下n-1个元素为有序
for(int i=site[x]+1;i<=n;i++){
a[i-1]=a[i];
}
a[n]=key;//把修改后的值放到最后
for(int i=n;i>1;i--){//插入 更新的值
if(!cmp(a[i-1],a[i])){
swap(a[i-1],a[i]);
}
}
//更新site
for(int i=1;i<=n;i++){
site[a[i].id]=i;
}
}
int main(){
int k,x,v;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&a[i].val);
a[i].id=i;
}
sort(a+1,a+n+1,cmp);//提前排序
for(int i=1;i<=n;i++){//更新位置关系
site[a[i].id]=i;
}
for(int i=1;i<=q;i++){
scanf("%d",&k);
if(k==2){
scanf("%d",&x);
printf("%d\n",site[x]);//输出位置
}else if(k==1){
scanf("%d%d",&x,&v);
upd(x,v);//更新
}
}
return 0;
}
Q.E.D.