法1

直接用\(sort\)模拟

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6;
int a[N],b[N],sum,sum1,x,y,n,m,l;
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++){
        cin>>l;
        if(l==1){
            cin>>x>>y;
            a[x]=y;
        }
        if(l==2){
            cin>>x;
            for(int j=1;j<=n;j++){
                if(a[j]==a[x]&&s){
                    sum++;
                    if(j==x) s=false;
                }
                b[j]=a[j];
            }
            sort(b+1,b+1+n);
            for(int j=1;j<=n;j++){
                if(b[j]==a[x]){
                    sum1++;
                    if(sum1==sum){
                        cout<<j<<endl;
                        break;
                    }
                }
            }
        }
    }
    return 0;
}

法2

使用线段树

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[8005];
struct node {
    int son[2], vis;
} t[5000005];
int k = 1;
void add(ll x) {
    int p = 1;
    ++t[p].vis;
    for (int i = 63; i >= 0; --i) {
        bool b = (x >> i) & 1;
        if (!t[p].son[b]) {
            t[p].son[b] = ++k;
        }
        p = t[p].son[b];
        ++t[p].vis;
    }
}
void move(ll x) {
    int p = 1;
    --t[p].vis;
    for (int i = 63; i >= 0; --i) {
        p = t[p].son[(x >> i) & 1];
        if (!p) {
            return ;
        }
        --t[p].vis;
    }
}
int query(ll x) {
    int res = 0, p = 1;
    for (int i = 63; i >= 0; --i) {
        bool b = (x >> i) & 1;
        if (b) {
            res += t[t[p].son[0]].vis;
        }
        p = t[p].son[b];
        if (!p) {
            return res;
        }
    }
    return res;
}
int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        add(1ll * (a[i] * n + i - 1));
    }
    for (int i = 1; i <= q; ++i) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, v;
            cin >> x >> v;
            move(1ll * (a[x] * n + x - 1));
            a[x] = v;
            add(1ll * (a[x] * n + x - 1));
        } else {
            int x;
            cin >> x;
            cout << query(1ll * (a[x] * n + x - 1) + 1) << '\n';
        }
    }
    return 0;
}