插入排序是一种非常常见且简单的排序算法。小 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 的询问,输出一行一个正整数表示答案。
3 4
3 2 1
2 3
1 3 2
2 2
2 3
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分。
思考程序中哪块耗时较多?可发现是在查询时,每次都需要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分。
此时再仔细分析下,注意题目中的数据范围“对于所有测试数据,保证在所有 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) 。
实际可发现,我们每次修改只更改了一个元素的值,也就是说,剩余元素在整体上是有序的,对于大部分都是有序的数据可以使用插入排序进行优化。我们可以将修改后的元素,插入到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.