记录编号	573802	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2021J]插入排序	最终得分	100
用户昵称	0429	是否通过	通过
代码语言	C++	运行时间	6.662 s
提交时间	2022-07-28 09:31:26	内存使用	3.71 MiB

#include<bits/stdc++.h>
using namespace std;
int n,q,a[8005],b[8005],num,x,v,ans;
int main()
{
		freopen("csp2021pj_sort.in", "r", stdin);
	 freopen("csp2021pj_sort.out", "w", stdout);
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			if(i==j||a[j]<a[i]||a[j]==a[i])b[i]++;
			else b[j]++;
		}
	}
	for(int i=0;i<q;i++)
	{
		cin>>num;
		if(num==1)
		{
			cin>>x;
			cin>>v;
			for(int i=1;i<=n;i++)
			{
				if(i==x)continue;
				if((a[i]<a[x]||a[i]==a[x]&&i<x)&&(a[i]>v||a[i]==v&&i>x))
				{
					b[i]++;b[x]--;
				}
				else if((a[i]>a[x]||a[i]==a[x]&&i>x)&&(a[i]<v||a[i]==v&&i<x))
				{
					b[i]--;b[x]++;
				}
			}
			a[x]=v;
		}
		if(num==2)
		{
			cin>>x;
			cout<<b[x]<<endl;
		}
	}return 0;}