CSP-J 2021 T2 题解

luqyou · 2021-10-27 13:27:36 · 个人记录

前言

本人这题零分，代码是回家之后写的。为什么零分呢？因为改了数字的位置。。。。。。

特别注意，本题不能改成快排，因为快排是不稳定的。

题意

给你 n 个数和 q 个操作，第一个操作可以使数字发生改变，第二个操作求排序后第 i 个数的新位置。

36pts

模拟每次操作，算法复杂度 O(q \times n^2)，即进行 q 次插排。

76pts

每次询问一个数排序后的位置，就扫一遍数组。扫到比它小的数 sum++，扫到相同的但位置比它前的也 sum++。

100pts

AC的关键在于操作1至多出现 5000 次，这样的话我们就可以先排序，再使用另外两个数组 b,c 记录排好序是第几个位置和排好序的第 i 个数原来在哪。

每当使用操作1时，我们就把要操作的那个数在排好序的数组，找到，然后进行修改，最后把这个数组中向后或向前移动维护好数组的有序性。即把经过的所有数的 b,c 数组修改一下，然后直接输出 c[x] 即可。

注意还有数字相等的情况，相等时比较 c 数组。

时间复杂度 O(5000n)。

code

#include<bits/stdc++.h>
using namespace std;
int a[8001],b[8001],c[8001];
int n,q;
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n-i;j++){
            if(a[j]>a[j+1]){
                swap(a[j],a[j+1]);
                swap(b[j],b[j+1]);
            }
        }
    }
    for(int i=1;i<=n;i++) c[b[i]]=i;
    for(int i=1;i<=q;i++){
        int ff,x,y,pos;
        scanf("%d",&ff);
        if(ff==1){
            scanf("%d%d",&x,&y);
            pos=c[x];
            a[pos]=y;
            if(pos!=n&&a[pos]>=a[pos+1]){
                while(1){
                    if(pos==n) break;
                    if(a[pos]==a[pos+1]&&b[pos]<b[pos+1]){
                        break;
                    }
                    if(a[pos]<a[pos+1]) break;
                    c[b[pos]]++;
                    c[b[pos+1]]--;
                    swap(b[pos],b[pos+1]);
                    swap(a[pos],a[pos+1]);
                    pos++;
                }
            }
            if(pos!=1&&a[pos]<=a[pos-1]){
                while(1){
                    if(pos==1) break;
                    if(a[pos]==a[pos-1]&&b[pos]>b[pos-1]) break;
                    if(a[pos]>a[pos-1]) break;
                    c[b[pos]]--;
                    c[b[pos-1]]++;
                    swap(b[pos],b[pos-1]);
                    swap(a[pos],a[pos-1]);
                    pos--;
                }
            }
        }
        else{
            scanf("%d",&x);
            printf("%d\n",c[x]);
        }
    }
    return 0;
}