复赛二：插入排序(sort)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include <iostream>
#include <algorithm>
using namespace std;

struct node{
    int id,num;
}a[8010];

bool cmp(node a, node b){
    if(a.num == b.num)return a.id<b.id;
     else return a.num<b.num;
}
int main(){
    int n,q,op,u,v;
    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--){
        cin>>op;
        if(op==1){ //操作1修改
              cin>>u>>v;
              for (int i = 1; i <=n; i++){
                if(a[i].id==u){
                    a[i].num=v;
                    break;
                }
              }
              sort(a+1,a+1+n,cmp);
        }else {
             cin>>u;
             for (int i = 1; i <=n; i++){
                 if(a[i].id==u){
                    cout<<i<<endl;
                    break;
                 }
             }
             

        }
    }
    
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include <iostream>
#include <algorithm>
using namespace std;

// 定义一个结构体 node，用来存储数组元素的下标 id 和对应的数值 num
struct node {
    int id, num;
} a[8010];  // a 数组，用于存储每个元素的下标和数值信息

int b[8010]; // b 数组，用于存储每个元素排序后的位置
int n;

// 比较函数，用于根据数值进行排序，若数值相同，则按原始下标排序
bool cmp(node a, node b) {
    if (a.num == b.num) return a.id < b.id;  // 数值相同，则按 id（即原始下标）升序
    else return a.num < b.num;  // 否则按数值升序
}

// 更新元素位置的函数，用于维护数组 a 的排序结构
void change(int pos) {
    // 向前检查，如果当前元素小于前一个元素，或者数值相同但 id 更小，则交换位置
    while (pos > 1) {
        if (a[pos].num > a[pos-1].num) break;  // 如果当前元素大于前一个元素，停止调整
        if (a[pos].num == a[pos-1].num && a[pos].id > a[pos-1].id) break;  // 如果数值相同但 id 较大，也停止调整
        swap(a[pos], a[pos-1]);  // 否则交换两元素位置
        b[a[pos].id] = pos;  // 更新 b 数组中的对应位置
        pos--;  // 继续向前调整
    }

    // 向后检查，如果当前元素大于后一个元素，或者数值相同但 id 更小，则交换位置
    while (pos < n) {
        if (a[pos].num < a[pos+1].num) break;  // 如果当前元素小于后一个元素，停止调整
        if (a[pos].num == a[pos+1].num && a[pos].id < a[pos+1].id) break;  // 如果数值相同但 id 较小，也停止调整
        swap(a[pos], a[pos+1]);  // 否则交换两元素位置
        b[a[pos].id] = pos;  // 更新 b 数组中的对应位置
        pos++;  // 继续向后调整
    }
    b[a[pos].id] = pos;  // 最后更新 b 数组中当前元素的最终位置
}

int main() {
    // 打开输入输出文件
    freopen("sort.in", "r", stdin);
    freopen("sort.out", "w", stdout);

    int q, op, u, v;
    cin >> n >> q;  // 读取数组长度 n 和操作次数 q

    // 读取初始数组 a，并将每个元素存储到 node 结构中
    for (int i = 1; i <= n; i++) {
        cin >> a[i].num;
        a[i].id = i;  // 记录每个元素的原始下标
    }

    // 对数组 a 进行排序，排序依据为数值大小，若相同则按原始下标排序
    sort(a + 1, a + 1 + n, cmp);

    // 初始化 b 数组，b[id] 记录的是原始下标为 id 的元素在排序后的新位置
    for (int i = 1; i <= n; i++) {
        b[a[i].id] = i;
    }

    // 处理 q 次操作
    while (q--) {
        cin >> op;  // 读取操作类型
        if (op == 1) {  // 操作类型 1：修改第 u 个元素的值为 v
            cin >> u >> v;
            a[b[u]].num = v;  // 修改第 b[u] 位置的元素数值为 v
            change(b[u]);  // 调整修改后元素在数组中的位置
        } else {  // 操作类型 2：查询第 u 个元素在排序后的新位置
            cin >> u;
            cout << b[u] << endl;  // 输出第 u 个元素在排序后的位置
        }
    }
}