题目

题目描述

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

H 老师给了一个长度为 $n$ 的数组 $a$，数组下标从 $1$ 开始，并且数组中的所有元素均为非负整数。小 Z 需要支持在数组 $a$ 上的 $Q$ 次操作，操作共两种，参数分别如下：

$1xv$：这是第一种操作，会将 $a$ 的第 $x$ 个元素，也就是 a x a_x ax​ 的值，修改为 $v$。保证 $1\le x\le n$， 1 ≤ v ≤ 1 0 9 1 \le v \le 10^9 1≤v≤109。注意这种操作会改变数组的元素，修改得到的数组会被保留，也会影响后续的操作。

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

H 老师不喜欢过多的修改，所以他保证类型 $1$ 的操作次数不超过 $5000$。

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

输入格式

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

第二行，包含 $n$ 个空格分隔的非负整数，其中第 $i$ 个非负整数表示 a i a_i ai​。

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

1
1
2

【数据范围】

对于所有测试数据，满足 $1\le n\le 8000$， 1 ≤ Q ≤ 2 × 10 5 1 \le Q \le 2 \times {10}^5 1≤Q≤2×105，$1\le x\le n$， 1 ≤ v , a i ≤ 1 0 9 1 \le v,a_i \le 10^9 1≤v,ai​≤109。

对于所有测试数据，保证在所有 $Q$ 次操作中，至多有 $5000$ 次操作属于类型一。

正文

第一眼看到此题，还以为是道排序模板题……很显然 $ccf$ 并不可能让考生 $happy$ ；

这道题有两种操作方式，如果用暴力排序：第一种 $O(1)$ ， 第二种$O(nlogn)$ ，得 $52$ 分；如果模拟插入：第一种 $O(1)$ ， 第二种$O(n)$ ，得 $76$ 分；我考场用的模拟：

#include 
using namespace std;
int n,q,a[20000];
int main(){cin>>n>>q;for(int i=1;i<=n;i++){cin>>a[i];}while(q--){int type,x,y;cin>>type;if(type==1){cin>>x>>y;a[x]=y;}else{cin>>x;int ans=1;for(int i=1;i<=n;i++){if(a[i]==a[x]&&i<x){ans++;}else if(a[i]<a[x]){ans++;}}cout<<ans<<endl;}}return 0;
}

虽然两种方法都不行，但是可以看到在题目中有一句话：

对于所有测试数据，保证在所有 $Q$ 次操作中，至多有 $5000$ 次操作属于类型一。

所以我们只能从类型一下手。首先创建一个结构体数组 a n a_n an​ ，其中有两个变量： $num$ 用来表示数据大小；$xb$ 表示 a i a_i ai​ 在原数组中的位置。再创建一个数组 w n w_n wn​ 用来表示 a i a_i ai​ 在排序后对应的是当前数组的 w i w_i wi​ 个位置；

开始时：

1. a数组从小到大排序；
2. 把w数组初始化；

在类型一中：

1. 先把a数组更新；
2. 枚举更新w数组；

在类型二中：

1. 输出w数组的第x个数据

AC CODE

#include
using namespace std;
int n,q,w[100005];
struct lyt{int num;int xb;
}a[100005];
bool cmp(lyt x,lyt y){if(x.num==y.num){return x.xb<y.xb;}else{return x.num<y.num;}
}
int main(){cin>>n>>q; for(int i=1;i<=n;i++){cin>>a[i].num;a[i].xb=i;}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){w[a[i].xb]=i;}while(q--){int type,x,y;cin>>type;if(type==2){cin>>x;cout<<w[x]<<endl;}else{cin>>x>>y;a[w[x]].num=y;for(int i=w[x];i>=2;i--){if(a[i].num<a[i-1].num||(a[i].num==a[i-1].num&&a[i].xb<a[i-1].xb)){swap(a[i],a[i-1]); }}for(int i=w[x];i<n;i++){if(a[i].num>a[i+1].num||(a[i].num==a[i+1].num&&a[i].xb>a[i+1].xb)){swap(a[i],a[i+1]); }}for(int i=1;i<=n;i++){w[a[i].xb]=i;}}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！