排序

阅读程序，题目给出的排序算法是稳定的，然而数组中存在相同元素，同时每次修改之后排序的时间不可接受。考虑解决这些问题。

首先对序列进行双关键字排序，值为第一关键字，下标为第二关键字，然后记录原先序列中下标为 $i$ 的元素排序后的下标，这样可以 $O(1)$ 回答每个询问。

对于修改操作有两种处理方法，时间复杂度同为 $O(n)$。

• 在排序后的序列中找到被修改的元素并修改，然后在序列上向左右各冒泡一轮。
• 把被修改的元素单独拎出来形成一个序列，其余元素形成一个序列，归并两个序列。

处理完毕后 $O(n)$ 更新答案序列。

记修改操作的次数为 $m$，总体时间复杂度 $O(n \log n + nm + q)$。

#include<bits/stdc++.h>
using namespace std;
pair<int,int> a[8'005];
int n,q,ans[8'005];
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].first);
        a[i].second=i;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) ans[a[i].second]=i;
    for(int i=1;i<=q;i++){
        static int x,y,opt;
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d%d",&x,&y);
            for(int j=1;j<=n;j++) if(a[j].second==x) a[j].first=y;
            for(int j=1;j<=n-1;j++) if(a[j]>a[j+1]) swap(a[j],a[j+1]);
            for(int j=n-1;j>=1;j--) if(a[j+1]<a[j]) swap(a[j],a[j+1]);
            for(int j=1;j<=n;j++) ans[a[j].second]=j;
        }
        else{
            scanf("%d",&x);
            printf("%d\n",ans[x]);
        }
    }
    return 0;
}