这一题暴力的做法是：

• 1操作$O(1)$修改
• 2操作$O(n \log n)$排序回答

很明显，这种做法是会超时的。

观察到题目中给出了一个很奇怪的条件：1操作次数$\le 5000$，那我们就可以利用这一点作文章。

首先，我们先将原数组进行排序，并用一个数组将 原数组中的元素 与 现数组中的元素 对应起来。

然后，对于每一次1操作，单点修改完后我们可以向左向右各冒泡一轮，这样可以维持数组有序。最后再更新原数组与现数组的关系。1操作的时间复杂度是$O(n)$级别的。

对于2操作，我们就可以利用原数组与现数组的关系数组$O(1)$进行回答。

这个算法的最坏时间复杂度为$O(5000n)$，可以通过。

AC code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=8005;
ll n,q,idx[N]; // 原数组中的第i项为现数组中的第idx[i]项
struct node{
	ll val,idx; // val为值，idx为下标
}a[N];
bool cmp(node x,node y){
	return x.val==y.val?x.idx<y.idx:x.val<y.val; // 插入排序是稳定的排序，即值相同的下标小的在前面
}
int main(){
	scanf("%lld%lld",&n,&q);
	for(ll i=1;i<=n;i++)
		scanf("%lld",&a[i].val),a[i].idx=i;
	sort(a+1,a+1+n,cmp); // 先进行一次排序
	for(ll i=1;i<=n;i++)
		idx[a[i].idx]=i; // 将 原数组中的元素 与 现数组中的元素 对应起来
	for(ll j=1,opt,x,v;j<=q;j++){
		scanf("%lld%lld",&opt,&x);
		if(opt==1){
			scanf("%lld",&v);
			ll index=idx[x]; // index为原数组中的第x项在现数组中的下标
			a[index].val=v; // 单点修改
			for(ll i=index;i>1;i--) // 向左冒泡一轮
				if(cmp(a[i],a[i-1])) // 注意这里a[i]和a[i-1]的顺序不能反，不然后果很严重！
					swap(a[i],a[i-1]);
			for(ll i=index;i<n;i++) // 向右冒泡一轮
				if(cmp(a[i+1],a[i])) // 注意这里a[i+1]和a[i]的顺序不能反，不然后果很严重！
					swap(a[i],a[i+1]);
			for(ll i=1;i<=n;i++) // 更新原数组与现数组的关系
				idx[a[i].idx]=i;
		}else
			printf("%lld\n",idx[x]); // 操作2 O(1)回答
	}
	return 0;
}

别问为啥cmp那儿我要反复强调，问就是因为我曾因为那个地方而全WA👀️