算法1

(暴力) $O(n^2q)$

我们只需在读入后对数组进行排序，之后在操作$1$（修改）时，查找$a_x$现在在的位置（该位置记为$i$），再把$a_i$改成$v$即可，由于修改之后有可能会影响到数组的单调性（从小到大）

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

/*
对于每次询问，都排序，操作1时，把ai改成v
*/
const int N = 8010;
int n, q;
int a[N];
int tmp[N];

int paixu(int x) {
    for(int i = 1; i <= n; i++)
        for(int j = i; j >= 2; j--) {
            if(tmp[j] < tmp[j - 1])
            {
                //如果x要被交换，将x更新
                if(j == x) x = j - 1;
                else if(j - 1 == x) x = j;
                int t = tmp[j - 1];
                tmp[j - 1] = tmp[j];
                tmp[j] = t;
            }
        }
    return x;
}

int main()
{
    freopen("sort.in", "r", stdin);
    freopen("sort.out", "w", stdout);
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    while(q --)
    {
        int op;
        cin >> op;
        if(op == 1)
        {
            int x, v;
            cin >> x >> v;
            a[x] = v;
        }
        else {
            int x;
            cin >> x;
            for(int i = 1; i <= n; i++) tmp[i] = a[i];
            cout << paixu(x) << endl;
        }
    }
    return 0;
}

算法2

时间复杂度$O(nqlogn)$

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

/*
对于每次询问，都排序，操作1时，把ai改成v
*/
const int N = 8010;
int n, q;
struct node {
    int id;
    int num;
};
node a[N];
bool cmp(node a, node b)
{
    if(a.num == b.num) return a.id < b.id;
    return a.num < b.num;
}
int main()
{
    freopen("sort.in", "r", stdin);
    freopen("sort.out", "w", stdout);
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].num;
        a[i].id = i;
    }
    sort(a + 1, a + 1 + n, cmp);
    while(q --)
    {
        int op;
        cin >> op;
        if(op == 1)
        {
            int x, v;
            cin >> x >> v;
            for(int i = 1; i <= n; i++)
                if(a[i].id == x)
                {
                    a[i].num = v;
                    break;
                }
            sort(a + 1, a + 1 + n, cmp);
        }
        else {
            int x;
            cin >> x;
            for(int i = 1; i <= n; i++){
                if(a[i].id == x) {
                    cout << i << endl;
                    break;
                }
            }

        }
    }
    return 0;
}

算法3

(暴力) $O(5000*Q)$

还是暴力现在开始优化啦~

因为我们的代码是会超时的，说明肯定还可以优化，那现在来找一下可以优化的点

可以优化的点：

1. 在查找和修改都要$for$循环找一次，这是很费时间的，那我们可以用一个$b$数组来建立一个映射，存这些值的序号，在查找和修改时就可以直接通过b数组查找，就会节省很多时间。
2. 我们发现，时间主要花在排序上。
   但是在改变值的地方，出了被改变的值，其他的都是有序的，所以可以优化，

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

/*
对于每次询问，都排序，操作1时，把ai改成v
*/
const int N = 8010;
int n, q;
struct node {
    int id;
    int num;
};
node a[N];
int b[N];

bool cmp(node a, node b)
{
    if(a.num == b.num) return a.id < b.id;
    return a.num < b.num;
}

//将pos这个位置的数，更新到它该待的位置
void change(int pos) { 
    while(pos > 1) { //往前滚
        if(a[pos].num == a[pos - 1].num && a[pos].id > a[pos - 1].id) break;
        if(a[pos].num > a[pos - 1].num) break;
        swap(a[pos], a[pos - 1]);
        b[a[pos].id] = pos; //pos往前了，所以b数组更新
        pos --;
    }
    while(pos < n) {
        if(a[pos].num == a[pos + 1].num && a[pos].id < a[pos + 1].id) break;
        if(a[pos].num < a[pos + 1].num) break;
        swap(a[pos], a[pos + 1]);
        b[a[pos].id] = pos;
        pos ++;
    }
}

int main()
{
    freopen("sort.in", "r", stdin);
    freopen("sort.out", "w", stdout);
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].num;
        a[i].id = i;
    }
    sort(a + 1, a + 1 + n, cmp);
    for(int i = 1; i <= n; i++)
        b[a[i].id] = i; //b[x] = y: 表示原数组中，下标是x的值，排序之后的位置是y
    while(q --)
    {
        int op;
        cin >> op;
        if(op == 1)
        {
            int x, v;
            cin >> x >> v;
            a[b[x]].num = v;
            change(b[x]); //对b[x]这个数字进行排序
            for(int i = 1; i <= n; i++)
                b[a[i].id] = i;
        }
        else {
            int x;
            cin >> x;
            cout << b[x] << endl;
        }
    }
    return 0;
}