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

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 8e3 + 5;
int a[maxn],cnt[maxn];
int n,m;
int read() {
    int s = 0;
    char c = getchar();
    for(;!isdigit(c);c = getchar());
    for(;isdigit(c);c = getchar())s = (s << 1) + (s << 3) + (c ^ '0');
    return s; 
}
void write(int x) {
    if(x > 9)write(x / 10);
    putchar(x % 10 + '0');
    return ;
}
void output(int x) {
    write(x);
    puts("");
    return ; 
}
void modify(int x,int v,int k) {
    for(int i = 1;i <= n;++ i) {
        if(i == x)continue ;
        cnt[i] += k * (v < a[i]||(a[i] == v&&x <= i));
    }
    return ;
}
int main() {
    freopen("csp2021pj_sort.in","r",stdin);
    freopen("csp2021pj_sort.out","w",stdout);
    n = read();
    m = read();
    for(int i = 1;i <= n;++ i) {
        a[i] = read();
    }
    for(int i = 1;i <= n;++ i) {
        for(int j = 1;j <= n;++ j) {
            cnt[i] += (a[j] < a[i]||(a[i] == a[j]&&j <= i));
        }
    }
    while(m --) {
        int v,op = read(),x = read();
        if(op & 1) {
            v = read();
            modify(x , a[x] , -1);
            modify(x , a[x] = v , 1);
            cnt[x] = 0;
            for(int i = 1;i <= n;++ i)cnt[x] += (a[i] < a[x]||(a[i] == a[x]&&i <= x));
        }
        else {
            output(cnt[x]);
        }
    }
    return 0;
}