2021JSP普及组第二题
题目：

思路：
题目要求排序后根据操作进行对应操作。

• 操作一需要显示某位置数据排序后的位置，所以需要定义结构体数组储存原数据的位置和数据本身
• 排序后所得数据要根据原位置输出排序后的位置，所以建立一个新的数组，数组下标对应数据原位置，值则为排序后的位置
• 第一部可以直接sort排序，但是操作后如果都用sort会超时。题干的插入排序不难想到，插入排序即是对已经排好序的数组进行插入操作后排序，一次插入后排序的复杂度为o(2n)
  1. 思路一：可以考虑判断操作的位置前后的数据大小，然后对数组前一段进行修改，或者后一段进行修改。但是由于相同数据还要判断数据原位置的大小，所以考虑的过程相对复杂
  2. 思路二：可以直接判断整个数组的内容，正着遍历和反着遍历（遍历是只能判断相邻两个元素的大小，所以反着再遍历一遍才能保持排序准确），而数据相同需要判断原位置大小（插入排序中，若数据相同，数据排序后的相对位置是不变的）
• 排序过程是对结构体进行排序，因此排序函数需要指针，而不是简单的形参

//定义结构体用来存储数组值和下标
//排序可以直接用sort
//修改后的数据修直接遍历处理 
#include
#include  
using namespace std;
struct node{
int n;
int id;
}arr[8001]; 
void swap(node *a,node *b);
bool cmp(node a, node b){
if(a.n!=b.n) return a.n<b.n;//升序排列 
else return a.id<b.id;
}
int main(){
int arr_k,k,b[8005];//分别储存数组长度，操作数
int k1,m,m1,m2;//分别储存操作序号和数据 
cin>>arr_k>>k;
for(int i=1;i<=arr_k;i++){
cin>>arr[i].n;
arr[i].id=i;
}
sort(arr,arr+arr_k+1,cmp);//排序 
//记录排序后的数据
for(int i=1;i<=arr_k;i++){
b[arr[i].id]=i;
} 
while(k--){
cin>>k1;
if(k1==2){
cin>>m;
cout<<b[m]<<endl;
}else{
cin>>m1>>m2;
arr[b[m1]].n=m2;
arr[b[m1]].id=m1;
for(int i=1;i<arr_k;i++){ 
if(cmp(arr[i],arr[i+1])==0){
swap(&arr[i],&arr[i+1]);
}
for(int i=arr_k;i>1;i--){  
if(cmp(arr[i-1],arr[i])==0){
swap(&arr[i],&arr[i-1]);
}
}
//更新排序
for(int i=1;i<=arr_k;i++){
b[arr[i].id]=i;
} 
}
}
return 0;
}
void swap(node *a,node *b){
int t1,t2;
t1=a->n,t2=a->id;
a->n=b->n,a->id=b->id;
b->n=t1,b->id=t2;
}