不建议使用插入排序

一开始事这样的，时间复杂度半爆没爆，差点给我气死

88分代码如下（映射做法）：

#include <bits/stdc++.h>
using namespace std;
struct node{
    int id,w;
}a[8010];
int n,q,ls[8010];
bool cmp(node a,node b){
    if(a.w==b.w) return a.id<b.id;
    return a.w<b.w;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i].w;
        a[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        ls[a[i].id]=i;
    }
    while(q--){
        int op,x;
        cin>>op>>x;
        if(op==1){
            int v;
            cin>>v;
            a[ls[x]].w=v;
            sort(a+1,a+n+1,cmp);
            for(int i=1;i<=n;i++){
                ls[a[i].id]=i;
            }
        }
        else{cout<<ls[x]<<endl;}
    }
    return 0;
}

最后改成了满分：

#include <bits/stdc++.h>
using namespace std;
struct node{
    int id,w;
}a[8010];
int n,q,ls[8010];
bool cmp(node a,node b){
    if(a.w==b.w) return a.id<b.id;
    return a.w<b.w;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i].w;
        a[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        ls[a[i].id]=i;
    }
    while(q--){
        int op,x;
        cin>>op>>x;
        if(op==1){
            int v,p=ls[x];
            cin>>v;
            a[p].w=v;
            while(p>1&&(a[p-1].w>a[p].w||a[p-1].w==a[p].w&&a[p-1].id>a[p].id)){
                swap(a[p],a[p-1]);
                p--;
            }
            while(p<n&&(a[p+1].w<a[p].w||a[p+1].w==a[p].w&&a[p+1].id<a[p].id)){
                swap(a[p],a[p+1]);
                p++;
            }
            for(int i=1;i<=n;i++){
                ls[a[i].id]=i;
            }
        }
        else{cout<<ls[x]<<endl;}
    }
    return 0;
}

说白了就是把刚才那个sort改为了局部调整，降低了时间复杂度
然后就过了