Algorithm/insert-sort/main.cc

#include <iostream>

using namespace std;

const int N = 10005;

pair<int, int> arr[N];
int beta[N];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i].first);
        arr[i].second = i;
    }
    sort(arr + 1, arr + n + 1);
    for (int i = 1; i <= n; i++) beta[arr[i].second] = i;
    while (m--) {
        int op, x, y;
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d%d", &x, &y);
            arr[beta[x]].first = y;
            for (int i = 1; i < n; i++) {
                if (arr[i] > arr[i + 1]) swap(arr[i], arr[i + 1]);
            }
            for (int i = n - 1; i >= 1; i--) {
                if (arr[i] > arr[i + 1]) swap(arr[i], arr[i + 1]);
            }
            for (int i = 1; i <= n; i++) beta[arr[i].second] = i;
        } else {
            scanf("%d", &x);
            printf("%d\n", beta[x]);
        }
    }
    return 0;
}