曲师大2023大一新生排位赛-B.Sort题解

题目描述

插入排序是一种非常常见且简单的排序算法。王同学是一名大一的新生，今天许师哥刚刚在上课的时候讲了插入排序算法。

假设比较两个元素的时间为 $O\left ( 1 \right )$ ，则插入排序可以以 $O\left ( n^2 \right )$ 的时间复杂度完成长度为 n� 的数组的排序。不妨假设这 n 个数字分别存储在 $a_1,a_2,......,a_n$ 之中，则如下伪代码给出了插入排序算法的一种最简单的实现方式：
下面是插入排序的示范代码：


for (int i = 1; i <= n; i++)
      for (int j = i; j >= 2; j--)
            if (a[j] < a[j-1]) {
		  int t = a[j-1];
		  a[j-1] = a[j];
		  a[j] = t;
	    }

为了帮助王同学更好的理解插入排序，许师哥给他留下了这么一道课后作业：

许师哥给了一个长度为 n 的数组 a，数组下标从 1 开始，并且数组中的所有元素均为非负整数。王同学需要支持在数组 a 上的 Q 次操作，操作共两种，参数分别如下：
1 x v：这是第一种操作，会将 a 的第 x 个元素，也就是 $a_x$ 的值，修改为 v。保证 $1 \leq x \leq n, 1 \leq v \leq 10 ^9$ 。注意这种操作会改变数组的元素，修改得到的数组会被保留，也会影响后续的操作。

2 x：这是第二种操作，假设许师哥按照上面的伪代码对 a 数组进行排序，你需要告诉许师哥原来 a 的第 x 个元素，也就是 $a_x$ ，在排序后的新数组所处的位置。保证 $1 \leq x \leq n$ 。注意这种操作不会改变数组的元素，排序后的数组不会被保留，也不会影响后续的操作。

许师哥不喜欢过多的修改，所以他保证类型 11 的操作次数不超过 50005000。

输入描述

第一行，包含两个正整数 $n,Q\left ( 1 \leq n \leq 8000,1 \leq Q \leq 2 \times 10^5 \right )$ ，表示数组长度和操作次数。
第二行，包含 n 个空格分隔的非负整数，其中第 i 个非负整数表示 $a_i \left ( 1 \leq a _i \leq 10^9 \right )$ 。
接下来 Q 行，每行 2∼3个正整数，表示一次操作，操作格式见【题目描述】。
输入数据保证 $1 \leq x \leq n, 1 \leq v \leq 10 ^9$ ，同时，在所有 Q 次操作中，至多有 5000 次操作属于类型一。

输出描述

对于每一次类型为 2 的询问，输出一行一个正整数表示答案。

样例

输入：

3 4
3 2 1
2 3
1 3 2
2 2
2 3

输出：

1
1
2

输入：

10 10
877332633 234569527 229171089 600324455 1458624 887548760 574229391 234569527 202374341 849045846
2 7
1 2 234569527
1 4 600324455
2 6
2 9
2 6
2 3
1 5 246345024
1 6 856960762
2 7

输出：

6
10
2
10
3
6

思路：

题目告诉我们至多5000次修改，很明显修改次数少，查询次数多。所以我们不能在查询时间进行排序操作的修改，但是可以在修改时间进行操作。
我们可以先对数据进行排序，原结构体数组记录排好序的下表，将排序结构体中对应好原数组的位置。
修改时间操作的理论：我将原来的数和修改后的数之间的下表进行修改，大于和小于这两个数的下表不需要修改，因为重新排序也不影响这两个数之外的位置，所以只需要修改原数和修改数区间内的下表即可。这样就可以可使用O(n)的时间复杂度完成这一操作
查询时间的理论：在修改时间同时维护这这两个结构体数组之间的对应关系，所以查询的时间复杂度是O(1)

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 8100;
struct node1
{
    int value,pxb;
}a[N];//原数组，对应的是该位置的值，该位置排序后的下标
struct node2
{
    int vlaue,yxb;
}b[N];//排序数组，对应的是该位置的值，该位置在原数组中对应的下标
bool cmp(node2 x,node2 y){
    if(x.vlaue == y.vlaue)
        return x.yxb < y.yxb;
    return x.vlaue < y.vlaue;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);cout.tie(NULL);
    int n,q;
    cin >> n >> q;
    for(int i = 1;i <= n;i++){
        int x;
        cin >> x;
        b[i].vlaue = x;
        b[i].yxb = i;
    }
    sort(b+1,b+1+n,cmp);
    // for(int i = 1;i <= n;i++){
    //     cout << b[i].vlaue << endl;
    // }
    for(int i = 1;i <= n;i++){
        a[b[i].yxb].value = b[i].vlaue;
        a[b[i].yxb].pxb = i;
    }
    // for(int i = 1;i <= n;i++){
    //     cout << a[i].pxb << " " << a[i].value << endl;
    // }
    while(q--){
        int op;
        cin >> op;
        if(op == 1){
            int x,v;
            cin >> x >> v;
            int yu = a[x].value;
            int xi = v;
            a[x].value = v;
            b[a[x].pxb].vlaue = v;
            int i = a[x].pxb;
            //两个循环只会进入一个
            //这个循环时说修改后的值比原来的值小了，用排序的数组往前找他自己的位置
            while(i != 1 &&( b[i].vlaue < b[i - 1].vlaue || (b[i].vlaue == b[i - 1].vlaue && b[i].yxb < b[i-1].yxb))){
                swap(b[i],b[i - 1]);
                a[b[i].yxb].pxb=i;
                a[b[i].yxb].value=b[i].vlaue;
                a[b[i - 1].yxb].pxb=i - 1;
                a[b[i - 1].yxb].value=b[i - 1].vlaue;
                i--;
            }
            //这个循环，修改后的值比原来的值大了，用排序数组往后找他自己的位置
            while(i != n &&( b[i].vlaue > b[i + 1].vlaue || (b[i].vlaue == b[i + 1].vlaue && b[i].yxb > b[i+1].yxb))){
                swap(b[i],b[i + 1]);//交换之后需要维护原来的对应关系
                a[b[i].yxb].pxb=i;
                a[b[i].yxb].value=b[i].vlaue;
                a[b[i + 1].yxb].pxb=i + 1;
                a[b[i + 1].yxb].value=b[i + 1].vlaue;
                i++;
            }
        }
        if(op == 2){
            int x;
            cin >> x;
            cout << a[x].pxb << "\n";
        }
    }
}

文章来源地址https://uudwc.com/A/Pdyoj