[CSP-J 2021] 插入排序

题目描述

插入排序是一种非常常见且简单的排序算法。小 Z 是一名大一的新生,今天 H 老师刚刚在上课的时候讲了插入排序算法。

假设比较两个元素的时间为 O(1)\mathcal O(1),则插入排序可以以 O(n2)\mathcal O(n^2) 的时间复杂度完成长度为 nn 的数组的排序。不妨假设这 nn 个数字分别存储在 a1,a2,,ana_1, a_2, \ldots, a_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;

为了帮助小 Z 更好的理解插入排序,小 Z 的老师 H 老师留下了这么一道家庭作业:

H 老师给了一个长度为 nn 的数组 aa,数组下标从 11 开始,并且数组中的所有元素均为非负整数。小 Z 需要支持在数组 aa 上的 QQ 次操作,操作共两种,参数分别如下:

1 x v1~x~v:这是第一种操作,会将 aa 的第 xx 个元素,也就是 axa_x 的值,修改为 vv。保证 1xn1 \le x \le n1v1091 \le v \le 10^9注意这种操作会改变数组的元素,修改得到的数组会被保留,也会影响后续的操作

2 x2~x:这是第二种操作,假设 H 老师按照上面的伪代码aa 数组进行排序,你需要告诉 H 老师原来 aa 的第 xx 个元素,也就是 axa_x,在排序后的新数组所处的位置。保证 1xn1 \le x \le n注意这种操作不会改变数组的元素,排序后的数组不会被保留,也不会影响后续的操作

H 老师不喜欢过多的修改,所以他保证类型 11 的操作次数不超过 50005000

小 Z 没有学过计算机竞赛,因此小 Z 并不会做这道题。他找到了你来帮助他解决这个问题。

输入格式

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

第二行,包含 nn 个空格分隔的非负整数,其中第 ii 个非负整数表示 aia_i

接下来 QQ 行,每行 232 \sim 3 个正整数,表示一次操作,操作格式见【题目描述】。

输出格式

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

样例 #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, 1

在修改操作之后,假设 H 老师进行了一次插入排序,则原序列的三个元素在排序结束后所处的位置分别是 3,1,23, 1, 2

注意虽然此时 a2=a3a_2 = a_3,但是我们不能将其视为相同的元素

【样例 #2】

见附件中的 sort/sort2.insort/sort2.ans

该测试点数据范围同测试点 121 \sim 2

【样例 #3】

见附件中的 sort/sort3.insort/sort3.ans

该测试点数据范围同测试点 373 \sim 7

【样例 #4】

见附件中的 sort/sort4.insort/sort4.ans

该测试点数据范围同测试点 121412 \sim 14

【数据范围】

对于所有测试数据,满足 1n80001 \le n \le 80001Q2×1051 \le Q \le 2 \times {10}^51xn1 \le x \le n1v,ai1091 \le v,a_i \le 10^9

对于所有测试数据,保证在所有 QQ 次操作中,至多有 50005000 次操作属于类型一。

各测试点的附加限制及分值如下表所示。

测试点 nn \le QQ \le 特殊性质
141 \sim 4 1010 1010
595 \sim 9 300300 300300
101310 \sim 13 15001500 15001500
141614 \sim 16 80008000 80008000 保证所有输入的 ai,va_i,v 互不相同
171917 \sim 19 80008000 80008000
202220 \sim 22 80008000 2×1052 \times 10^5 保证所有输入的 ai,va_i,v 互不相同
232523 \sim 25 80008000 2×1052 \times 10^5

分析

阅读题面,可知题目要我们输出的是原来aa 的第xx个元素,也就是axa_x ,在排序后的新数组所处的位置。

题目中除了查询操作以外还有一个操作为修改操作:将 aa 的第 xx 个元素,也就是 axa_x 的值,修改为 vv

其中,修改操作会改变原数组的内容,且修改的是原数列位置上的内容,并修改内容会被保留下来。意味着元素修改可能就会影响数列的排序。

暴力思路

保留原序列aa,开一个数组bb,每次修改在原序列aa上进行修改;查询时,则将aa中存储到bb中,对数列bb

进行排序,再输出axa_x在排序后的位置即可。

注意相同值但不同位置元素不能视为相同的元素,所以排序时要注意保持原序列相同元素值的相对位置。

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)。此时数据范围最大n8000Q2×105n \le8000,Q\leq 2\times10^5 ,会超时。得到52分。

优化1.0

思考程序中哪块耗时较多?可发现是在查询时,每次都需要O(nlogn)O(nlogn)的复杂度进行排序,这块用时较长。在这思考如何优化该过程。我们的目的是找到axa_x的位置即可,实际上不需要你去将其他元素排序好,此时只需盯着axa_x即可,统计在整个序列中排在它前面的元素有几个,就能知道它在第几个位置了。

	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)。比之前的小,但是还是会超时。得到76分。

优化2.0

此时再仔细分析下,注意题目中的数据范围“对于所有测试数据,保证在所有 QQ 次操作中,至多有 50005000 次操作属于类型一。”操作类型一为修改操作,类型二维查询操作。之前每次都是O(n)O(n)的复杂度确定元素位置,O(1)O(1)的复杂度进行修改。查询的操作比较多,若能再次降低查询时的复杂度,就能优化整体的时间了。

可发现,修改操作远少于查询的操作,若针对一个有序的数列查找原来元素的当前位置关系,这是可以较方便的构建映射关系的。

//site[x]:原序列a[x]在排好后的位置
for(int i=1;i<=n;i++){
    site[a[i].id]=i;
}

我们在执行完操作一,修改完原序列中的元素值之后,再把序列排序下,然后再重新构建位置关系。把用时长的执行的次数少些。

此时还是只有76,因为对于n来说范围也是达到了8000800050005000操作一依然会超。因为排序用时为O(nlogn)O(nlogn)

优化3.0

实际可发现,我们每次修改只更改了一个元素的值,也就是说,剩余元素在整体上是有序的,对于大部分都是有序的数据可以使用插入排序进行优化。我们可以将修改后的元素,插入到n1n-1个有序元素中。排序复杂度就能降为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.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)