记录编号	574376	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	3616.[CSP 2021J]插入排序	最终得分	100
用户昵称	Lesater	是否通过	通过
代码语言	C++	运行时间	5.998 s
提交时间	2022-08-05 16:13:27	内存使用	3.79 MiB

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int w;
    int nub;
    int to;
};
Node a[8001];
Node b[8001];
long long n,q;
bool cmp(Node a,Node b)
{
    if(a.w<b.w||(a.w==b.w&&a.nub<b.nub)) return true;
    return false;
}
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].w;
        b[i].w=a[i].w;
        b[i].nub=i;
    }
    sort(b+1,b+1+n,cmp);
    for(int i=1;i<=n;++i)
        a[b[i].nub].to=i;
    int k,x,y;
    while(q>0)
    {
        q--;
        cin>>k;
        if(k==1)
        {
            cin>>x>>y;
            a[x].w=y;
            int t=a[x].to;
            b[t].w=y;
            for(int i=t;i<n;++i)
            {
                if(b[i].w>b[i+1].w||
                (b[i].w==b[i+1].w&&b[i].nub>b[i+1].nub)) 
                {                  
                    a[x].to=i+1;
                    a[b[i+1].nub].to=i;
                    Node l=b[i];
                    b[i]=b[i+1];
                    b[i+1]=l;
                }
            }
            for(int i=t;i>1;--i)
            {
                if(b[i].w<b[i-1].w||
                (b[i].w==b[i-1].w&&b[i].nub<b[i-1].nub)) 
                {                    
                    a[x].to=i-1;
                    a[b[i-1].nub].to=i;
                    Node l=b[i];
                    b[i]=b[i-1];
                    b[i-1]=l;
                }
            }
        }
        if(k==2)
        { 
            cin>>x;
            cout<<a[x].to<<endl;
        }
    }
    return 0;
}