P7910 [CSP-J 2021] 插入排序 题解

SafariMo · 2023-12-10 08:58:50 · 题解

题解区没有的做法。

• 对于每个修改操作，我们直接修改。
• 对于每个查询操作，我们暴力查询，从头向后查找，按题意模拟即可。

时间复杂度 \mathcal{O}(nq)。

#include<iostream>
#include<cstdio>
using namespace std;
int a[10011];
int main()
{
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=q;i++){
        int xx;
        scanf("%d",&xx);
        if(xx==1){
            int x,v;
            scanf("%d%d",&x,&v);
            a[x]=v;
        } 
        else {
            int x;
            scanf("%d",&x);
            int w=a[x];
            int sum=n;
            for(int j=1;j<x;j++){
                if(a[j]>w){
                    sum--;
                }
            }
            for(int j=x+1;j<=n;j++){
                if(a[j]>=w) sum--;
            }
            printf("%d\n",sum);
        }
    }
    return 0;
}

Submission