题解(最优)

可以发现，对于一个已经有序的数列，单点修改一个值，我们可以通过前后冒泡各一次来保持有序.

我们可以从前往后冒泡，再次维持了数列的有序。这样的操作是 O(n) 的。

同样的，我们可以维护一个有序数列，并记录原下标与先下标之间的关系（用数组记录），每次修改后更新这种关系。

这样，修改操作是 O(n) 的，查询是 O(1) 的。完结撒花。

#include <bits/stdc++.h>
using namespace std;

int n,q;
struct node{
    int id,num;
}a[8005];
int t[8005]; //t[i]表示原数组的第i个元素在新数组的位置

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

int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i].num;
        a[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        t[a[i].id]=i;
    }
    for(int i=1;i<=q;i++){
        int ot,x,v;
        cin>>ot;
        if(ot==1){
            cin>>x>>v;
            a[t[x]].num=v;
            for(int i=2;i<=n;i++){
                if(cmp(a[i],a[i-1])){
                    node tt=a[i-1];
                    a[i-1]=a[i];
                    a[i]=tt;
                }
            }//后扫
            for(int i=n;i>1;i--){
                if(cmp(a[i],a[i-1])){
                    node tt=a[i-1];
                    a[i-1]=a[i];
                    a[i]=tt;
                }
            }//前扫
            for(int i=1;i<=n;i++){
                t[a[i].id]=i;
            }//更新关系
        }else{
            int x;
            cin>>x;
            cout<<t[x]<<endl;
        }
    }
    return 0;
}