离散化

#include<bits/stdc++.h>
using namespace std;
const int N=8010;
int n,q,b[N];//用b数组来存原来的下标     
int num,x,v;
struct node{
    int id;
    int num;
}a[N];//a为原数组 
bool cmp(node a,node b)
{
    if(a.num==b.num) 
        return a.id<b.id;
    else
        return a.num<b.num;
}
void jiaohuan(int pos) //pos是position简写  
{
    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;
        swap(a[pos-1],a[pos]);  //ID和num都交换  
        b[a[pos].id]=pos; //更新位置 
        pos--;
    }
    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;
        swap(a[pos+1],a[pos]); 
        b[a[pos].id]=pos;
        pos++;
    }
    b[a[pos].id] = pos; //把最后一个（或第一个）补上  
}
int main()
{
    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数组来存第i个数的下标的下标，可以理解为形成一个映射关系  
    }   
    while(q--)
    {
        cin>>num;
        if(num==1) //找到原数组a的第x个元素，更换为v  （可以更改数组） 
        {
            cin>>x>>v;
            a[b[x]].num=v;//按题意模拟 
            change(b[x]);
            //sort(a+1,a+n+1,cmp);
            //for(int i=1;i<=n;i++)
            //  b[a[i].id] = i;
        } 
        if(num==2) //从小到大排序，找到排序前数组a的第x个元素的新位置  （不更改数组） 
        {
            cin>>x;
            cout<<b[x]<<endl;
        }
    }
    return 0;
}