2553

其他 C++ 公开

#include <iostream>
using namespace std;

int n, q;
int a[8005];
int rk[8005];   // rk[i]：a[i]排序后所处的位置

// 值为p、下标为x的元素，是否排在值为r、下标为y的元素前面
bool front(int p, int x, int r, int y) {
    if (p != r) return p < r;   // 值小的在前
    return x < y;               // 值一样，下标小的在前（稳定排序）
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 初始化：对每个i，数有多少个元素排在它前面
    for (int i = 1; i <= n; i++) {
        rk[i] = 1;
        for (int j = 1; j <= n; j++) {
            if (j != i && front(a[j], j, a[i], i)) rk[i]++;
        }
    }

    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, v;
            cin >> x >> v;
            int old = a[x];     // 修改前的值
            a[x] = v;           // 修改

            // 先重新算x自己的位置
            rk[x] = 1;
            for (int i = 1; i <= n; i++) {
                if (i != x && front(a[i], i, a[x], x)) rk[x]++;
            }

            // 再修正别的元素
            for (int i = 1; i <= n; i++) {
                if (i == x) continue;
                bool before = front(old, x, a[i], i);   // 修改前，x在i前面吗
                bool after  = front(v, x, a[i], i);     // 修改后，x在i前面吗
                if (!before && after) rk[i]++;          // 新增了一个排在前面的
                if (before && !after) rk[i]--;          // 少了一个排在前面的
            }
        } else {
            int x;
            cin >> x;
            cout << rk[x] << "\n";   // O(1)直接回答
        }
    }
    return 0;
}