就光用了个vector模拟平衡树

#include<bits/stdc++.h>
using namespace std;
int n,Q,x,v;
int a[8010];
map<int,int> mp;
vector<int> g;
int main()
{
	cin>>n>>Q;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		g.insert(lower_bound(g.begin(),g.end(),a[i]),a[i]);
		mp[a[i]]++;
	}
	while(Q--)
	{
		int op;
		scanf("%d",&op);
		if(op==1)//修改 
		{
			scanf("%d%d",&x,&v);
			int t=a[x];
			a[x]=v;
			mp[t]--;
			mp[v]++;
			g.erase(lower_bound(g.begin(),g.end(),t));
			g.insert(lower_bound(g.begin(),g.end(),v),v);
		}
		if(op==2)
		{
			int cnt=0;
			scanf("%d",&x);
			for(int i=1;i<x;i++)
			{
				if(a[i]==a[x])
				cnt++;
			}
			int p=lower_bound(g.begin(),g.end(),a[x])-g.begin()+1;
			printf("%d\n",p+cnt);
		}
	}
	return 0;
}