记录编号	571698	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2021J]插入排序	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	3.496 s
提交时间	2022-06-12 12:04:51	内存使用	3.79 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=8000+5;
struct sdf{
	int num,pt;
	bool operator<(const sdf&x)const{
		if (x.num!=num)return num<x.num;
		return pt<x.pt;
	}
};
int n,q;
int a[N],ans[N],b[N],num[N];
sdf p[N];
int t,x,y,lst;
int main(){
    freopen ("csp2021pj_sort.in","r",stdin);
    freopen ("csp2021pj_sort.out","w",stdout);
    scanf("%d%d",&n,&q);
    for (int i=1;i<=n;i++){
        scanf("%d",&b[i]);
        num[i]=i;
        p[i]={b[i],i};
    }
    for (int i=1;i<=n;i++){
    	for (int j=i;j>=2;j--){
    		if (b[j]<b[j-1]){
    			swap(b[j],b[j-1]);swap(num[j],num[j-1]);
			}
		}
	}
	for (int i=1;i<=n;i++)ans[num[i]]=i;
    for (int i=1;i<=q;i++){
//    	for (int i=1;i<=n;i++)cout<<ans[i]<<' ';
//    	cout<<endl;
        scanf("%d",&t);
        if (t==1){
            scanf("%d%d",&x,&y);
            sdf lst=p[x];
            p[x].num=y;
            ans[x]=1;
            for (int j=1;j<=n;j++){
            	if (j==x)continue;            
            	if (p[j]<p[x])ans[x]++;
            	if (lst<p[j]&p[j]<p[x])ans[j]--;
            	if (p[j]<lst&&p[x]<p[j])ans[j]++;
            	
			}
        }
        else{
            scanf("%d",&x);
            printf("%d\n",ans[x]);
        }
    }
    return 0;
}