CSP-J2 2021 T2 题解

今年的题目非常简单，但是这道题在考场上死活没做出来... 现在终于做出来了，哈哈哈！
这道题简单就在于，一共只会有两种操作。其中第一种操作的a[x] v表示的就是将a[x]这个数更新为v这个值。第二种操作就是查找这一个数在原数组中的位置。
我们不妨先对整个程序进行排序（使用<algorithm>中的sort()函数即可），这样在后面就可以运用插入排序的思想。

Step 1

编写一个结构体，里面存放这个数的位置id以及它原来的值value，并且用一个a[]数组存储（不需要太大，因为最大的n只会有8000）。

struct node{
    int id;
    int val;
} a[8005];

编写一个cmp()函数，用于数组最开始的排序。（根据题意，如果两个数的值相同，最终返回的是id小数的排在前面）

bool cmp(node a,node b){
    if (a.val==b.val) return a.id<b.id;
    else return a.val<b.val;
}

定义一些变量，其中n和q就是题目中所给出的，op代表的是操作类型，pos表示的是当前更改的数的位置，x和y表示的是数组下标和需要更改的新的值，c[]数组是用于存储该数在原数组中的位置。

---

Step 2

首先判断状态，如果输入的是1，那么就说明这是在执行第一种操作。第一种操作就是寻找数组中的一个数并替换它的值。当我们读到第一个数字是1，那么我们再往后读两个数，通过循环的方式更新这个数的值以及下标位置。

for(register int j=1;j<=n;j++){
    if(a[j].id==x){
        a[j].val=y;
        pos=j;
        break;
    }
}

如果输入的是2，也就是查询该数在原数组中的位置，那就直接查询c[]数组中这个数的位置。

x=read();
printf("%d\n",c[x]);

---

Step 3

现在进行排序操作。因为这个数是需要经过排序，若在此进行sort()排序会增加操作时间，于是在最开始进行的排序就很有必要。
因为数组是排好序了的，我们只需要通过插入排序的思想来和左右对比，知道找到我们可以插入的位置。因此，我们可以从pos（当前更改的数的位置）开始，向左或向右寻找。不用担心会把两个区间找完，因为我们有cmp()函数。如果哪一个区间是排序好了的，就不会执行（cmp()返回假就说明排序好了）。

for(register int j=pos;j<=n-1;j++){
    if(!cmp(a[j],a[j+1])){
        swap(a[j],a[j+1]);
    }
    else break;
}
for(register int j=pos-1;j>=1;j--){
    if(!cmp(a[j],a[j+1])){
        swap(a[j],a[j+1]);
    }
    else break;

}

当然，我们也需要更新原数组的id，因为我们进行了排序。

for(register int j=1;j<=n;j++) {
        c[a[j].id] = j;
    }  
}

于是，就大功告成了~

---

完整程序

#include <cstdio>
#include <iomanip>
#include <cstring>
#include <algorithm>
using namespace std;
int n,q,op,x,y,pos;
int read(){
    int f=1,x=0;
    char a=getchar();
    while(a<'0'||a>'9'){
        if(a=='-') f=-1;
        a=getchar();
    }
    while( a>='0' && a<='9'){
        x=x*10+a-'0';
        a=getchar();
    }
    return f*x;
}
struct node{
    int id;
    int val;
}a[8005];
bool cmp(node a,node b){
    if(a.val==b.val) return a.id<b.id;
    if(a.val<b.val) return true;
    return false;
}
int c[8005];
int main(){
    n=read();q=read();
    for(register int i=1;i<=n;++i){
        a[i].val=read();
        a[i].id=i;
    }  

    sort(a+1,a+1+n,cmp);

    for(register int j=1;j<=n;j++) {
        c[a[j].id]=j;
    }
       
    for(register int i=1;i<=q;++i){
        op=read();
        if(op==1){
            x=read();y=read();
       
            for(register int j=1;j<=n;j++){
                if(a[j].id==x){
                    a[j].val=y;pos=j;break;
                }
            }
            for(register int j=pos;j<=n-1;j++){
                if(!cmp(a[j],a[j+1])){
                    swap(a[j],a[j+1]);
                }
                else break;
            }
            for(register int j=pos-1;j>=1;j--){
                if(!cmp(a[j],a[j+1])){
                    swap(a[j],a[j+1]);
                }
                else break;
            }
            for(register int j=1;j<=n;j++) {
                c[a[j].id] = j;
            }  
        }
        else {
            x=read();
            printf("%d\n",c[x]);
        }
    }
    return 0;
}