这题直接暴力基数排序就可以过

复杂度不直接O(5000 * 5 * n + m)

可惜考试时傻了 写正解写挂了 只写了个暴力O(5000 * n ^ 2 + m)

洛谷AC代码

#include<iostream>
#include<cstdio>
using namespace std;
struct point{
	int pm,v;
}b[1000010];
struct edge{
	int next;
	point to;
}e[1000010];
int head[256];
int a[1000010];
int place[1000010];
int n,m,f,x,y;
void sort(){
	for(int i=1;i<=n;i++)b[i].v=a[i],b[i].pm=i;
	for(int i=0,p=n;i<40;i+=8,p=n){
		for(int j=1;j<=n;e[j].next=head[((long long)b[++j].v>>i)&255])
			head[((long long)b[j].v>>i)&255]=j,e[j].to=b[j];
		for(int j=255;j>-1;j--)
			for(;head[j];head[j]=e[head[j]].next)
				b[p--]=e[head[j]].to;
	}
	for(int i=1;i<=n;i++)place[b[i].pm]=i;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	sort();
	while(m--){
		scanf("%d",&f);
		if(f==1){
			scanf("%d%d",&x,&y);
			if(a[x]!=y)a[x]=y,sort();
		}else if(f==2){
			scanf("%d",&x);
			cout<<place[x]<<endl;
		}
	}
	return 0;
}