题目全部思路和题解 看完 正解在最后

刚开始的思路，就是大模拟，将题目意思全部模拟下来
侥幸心理以为不会超时

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

const int maxn = 2e5 + 10;

struct node{
    int sl;
    int xb;
}a[maxn];

struct note{
    int sl3;
    int xb3;
}m[maxn];

int n, q;

int f(int x, int y){
    for (int i = 1; i <= n; i ++){
        m[i].sl3 = a[i].sl;
        m[i].xb3 = a[i].xb;
    }
    for (int i = 1; i <= n; i ++){
		for (int j = i; j >= 2; j --){
			if (m[j].sl3 < m[j - 1].sl3) {
				swap(m[j - 1], m[j]);
			}
        }
    }
    for (int i = 1; i <= n; i ++){
        if (m[i].sl3 == x && m[i].xb3 == y){
            return i;
        }
    }
}

int main(){
    cin >> n >> q;
    for (int i = 1; i <= n; i ++){
        cin >> a[i].sl;
        a[i].xb = i;
    }
    while (q --){
        int o;
        cin >> o;
        if (o == 1){
            int x, v;
            cin >> x >> v;
            a[x].sl = v;
        }else if (o == 2){
            int x;
            cin >> x;
            cout << f(a[x].sl, a[x].xb) << endl;
        }
    }
    return 0;
}

不过时间复杂度是 O(n方q) 会超时的

其次呢就是想用比当前数字小的总数和再加1就是当前的下标

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

//时间为O(nq);
//是用比数字小的再加一就是当前的下标

const int maxn = 2e5 + 10;
int a[maxn];

int main(){
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    while (q --){
        int o;
        cin >> o;
        if (o == 1){
            int x, v;
            cin >> x >> v;
            a[x] = v;
        }else if (o == 2){
            int x;
            cin >> x;
            int ans = 1;
            int w = a[x];
            for (int i = 1; i < x; i ++){
                if (a[i] <= w) ans ++;
            }
            for (int i = x + 1; i <= n; i ++){
                if (a[i] < w) ans ++;
            }
            cout << ans << endl;
        }
    }
    return 0;
}

时间复杂度是O(nq)
ACgo太厉害了 其实过不了

最后 我们想提前排好序，求出每一个下标排序后对应的下标
如果添加 就插进来，然后对应下标全部往后移
这样时间复杂度就很小了

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

//思路：提前排好序，求出每一个下标排序后对应的下标
    //如果添加 就插进来，然后对应下标全部往后移

const int N = 2e5 + 10;
int n, m, ans[N];

struct node{
    int num;
    int id;
}a[N];

bool cmp(node u, node v){
    if (u.num != v.num) return u.num < v.num;
    return u.id < v.id;
}

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i ++){
        cin >> a[i].num;
        a[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp);

    for (int i = 1; i <= n; i ++){
        ans[a[i].id] = i;//ans[原始下标] = 对应排名
    }

    while (m --){
        int t;
        cin >> t;
        if (t == 1){
            int x, y;
            cin >> x >> y;
            int id = ans[x];//单独对于这一个位置去调整
            a[id].num = y;
            while (id > 1 && !cmp(a[id - 1], a[id])){//往前调整
                swap(a[id - 1], a[id]);
                id --;
            }
            while (id < n && !cmp(a[id], a[id + 1])){//往后调整
                swap(a[id], a[id + 1]);
                id ++;
            }
            for (int i = 1; i <= n; i ++){
                ans[a[i].id] = i;
            }
        }else{
            int x;
            cin >> x;
            cout << ans[x] << endl;
        }
    }
    return 0;
}

这样的话就全部AC了