个人觉得一下两种写法都是 $O(n)$ 修改，$O(1)$ 查询，思路也一样，为什么一种能过另一种就T了呢？

TLE:

#include<bits/stdc++.h>
using namespace std;
int n,q,idx[8005],opt,x,y,j=0;
struct node
{
	int val,id;
	bool operator<(const node &o)const
	{
		if(val!=o.val) return val<o.val;
		return id<o.id;
	}
}b[8005];
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&b[i].val);
	for(int i=1;i<=n;i++) b[i].id=i;
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++) idx[b[i].id]=i;
	while(q--)
	{
		scanf("%d",&opt);
		if(opt==1)
		{
			scanf("%d%d",&x,&y);
			b[idx[x]].val=y;
			j=idx[x];
			while(b[j-1].val>b[j].val||b[j+1].val<b[j].val||(b[j-1].val==b[j].val&&b[j-1].id>b[j].id)||(b[j+1].val==b[j].val&&b[j+1].id<b[j].id))
			{
				if(b[j-1].val>=b[j].val)
				{
					if(j-1<1) break;
					idx[x]--,idx[b[j-1].id]++;
					swap(b[j-1],b[j]);
					j--;
				}
				else
				{
					if(j+1>n) break;
					idx[x]++,idx[b[j+1].id]--;
					swap(b[j+1],b[j]);
					j++;
				}
			}
		}
		if(opt==2)
		{
			scanf("%d",&x);
			printf("%d\n",idx[x]);
		}
	}
	return 0;
}

将改变的数沿着左边或右边，逐个换位。

AC:

#include<bits/stdc++.h>
using namespace std;
int n,q,idx[8005],opt,x,y;
struct node
{
	int val,id;
}b[8005];
bool cmp(node u,node v)
{
	if(u.val!=v.val) return u.val<v.val;
	return u.id<v.id;
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&b[i].val);
	for(int i=1;i<=n;i++) b[i].id=i;
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++) idx[b[i].id]=i;
	while(q--)
	{
		scanf("%d",&opt);
		if(opt==1)
		{
			scanf("%d%d",&x,&y);
			b[idx[x]].val=y;
			for(int i=2;i<=n;i++) if(cmp(b[i],b[i-1])) swap(b[i],b[i-1]);
			for(int i=n;i>=2;i--) if(cmp(b[i],b[i-1])) swap(b[i],b[i-1]);
			for(int i=1;i<=n;i++) idx[b[i].id]=i;
		}
		if(opt==2)
		{
			scanf("%d",&x);
			printf("%d\n",idx[x]);
		}
	}
	return 0;
}

第一篇题解代码，不必多言。

为什么？？？