洛谷P7910

#include 
using namespace std;
const int N=8005;
int o[N],h[N];
int ph[N],hp[N];
int n,q; 
inline int read(){//快速读入 
	int res=0,f=1;//res记录数值，l记录正负
	char c;
	c=getchar();
	while(c>'9' || c<'0'){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(c>='0' && c<='9'){
		res=res*10+c-'0';
		c=getchar();
	}
	return res*f;
}
int  main(){	
	n=read();q=read();
	for(int i=1;i<=n;i++){
		o[i]=read();
		h[i]=o[i],ph[i]=hp[i]=i;//输入时初始化
	}
	for (int i = 1; i <= n; i++)
		for (int j = i; j >= 2; j--)
			if (h[j] < h[j-1]){
				swap(ph[hp[j]],ph[hp[j-1]]);
				swap(hp[j],hp[j-1]);//下标都应交换
				swap(h[j],h[j-1]);//交换原数组数值
			}
	int qu,id,va;//question 序号 value
	for(int i=1;i<=q;i++){
		qu=read();
		id=read();
		if(qu==1){
			va=read();
			o[id]=va;
			h[ph[id]]=va;//改变数值
			int k=ph[id];
			while(h[k-1]>h[k] || h[k-1]==h[k] && hp[k]h[k+1] || h[k]==h[k+1] && hp[k]>hp[k+1]){//右侧循环
				swap(ph[hp[k]],ph[hp[k+1]]);
				swap(hp[k],hp[k+1]);
				swap(h[k],h[k+1]);//有些变动
				k++;
				if(k>=n) break;
			}			
		}
		else printf("%dn",ph[id]);
	}	
	return 0;
}