用一个数组$num[]$储存每个数排序后的位置。

输入$a_i$,更新$num[]$(num[a[i].id] = i)。

• 操作1: 先直接修改:a[num[x]].x = v 然后排序。要用插入排序,而不是全部重新排序,因为其他未修改的数已经是单调递增的了。 排序后再更新一次$num[]$。
• 操作2: 直接输出$num_x$即可。

code:

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

struct node
{
	int x,id;
}a[8001];

int n,q,x,v;
int num[8001];//数排序后的位置

bool cmp(node x,node y)
{
	if(x.x != y.x) return x.x < y.x;//排序
	else return x.id < y.id;
}

void turn()
{
	for(int i = 1;i <= n;i++)
	{
		num[a[i].id] = i;//更新
	}
	return;
}

signed main()
{
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	scanf("%d%d",&n,&q);
	for(int i = 1;i <= n;i++)
	{
		scanf("%d",&a[i].x); 
		a[i].id = i;
	}
	sort(a + 1,a + n + 1,cmp);
	turn();
	while(q--)
	{
		int o;
		scanf("%d",&o);
		if(o == 1)
		{
			scanf("%d%d",&x,&v);
			a[num[x]].x = v;//直接修改
			for(int i = 1;i < n;i++)//排序
			{
				if(a[i].x > a[i + 1].x)
				{
					swap(a[i],a[i + 1]);
				}
				else if(a[i].x == a[i + 1].x && a[i].id > a[i + 1].id)
				{
					swap(a[i],a[i + 1]);
				}
			}
			for(int i = n - 1;i > 0;i--)
			{
				if(a[i].x > a[i + 1].x)
				{
					swap(a[i],a[i + 1]);
				}
				else if(a[i].x == a[i + 1].x && a[i].id > a[i + 1].id)
				{
					swap(a[i],a[i + 1]);
				}
			}
			turn();
		}
		else
		{
			scanf("%d",&x);
			printf("%d\n",num[x]);//输出
		}
	}
	return 0;
}