题解 | 小红的区间查询

#include <bits/stdc++.h>
using namespace std;

const int N   =  210;
int n,q,a[N],s[N][N];

void add(int l,int x,int k){
    for(int i  =  l;i<=n;i+=(i&-i)){
        s[i][x]+=k;
    }
}

int sum(int r,int x){
    int res =  0;
    for(int i =  r;i;i-=(i&-i)){
        res += s[i][x];
    }
    return res;
}

int main(){
    cin>>n>>q;
    for(int i  =  1;i<=n;i++) {
        cin>>a[i];
        add(i,a[i],1);
    }

    while(q--){
        int op,i,x;
        cin>>op>>i>>x;
        if(op==1){
            int pro  = a[i];
            a[i]  = x;
            add(i,pro,-1);
            add(i,x,1);
        }
        else{
            cout<<sum(i,x)<<"\n";
        }
    }

    return 0;
}