快速排序($mnlog^n$52pts）

• 使用结果体储存对应的信息，每次更新以后使用快速排序更新信息。

#include<bits/stdc++.h>
using namespace std;
const int N=8010;
struct Node{
    int num;
    int id;
}s[N];
bool cmp(Node a,Node b) //排序规则
{
    if(a.num<b.num) return true; //数字小的在前面
    if(a.num==b.num&&a.id<b.id) return true; //数字相同，编号小的在前面
    return false;
}
int main()
{
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i].num;
        s[i].id=i;
    }
    sort(s+1,s+n+1,cmp); //排序
    while(q--)
    {
        int op,x,v;
        cin>>op;
        if(op==1)
        {
            cin>>x>>v;
            for(int i=1;i<=n;i++) //找到对应位置
            {
                if(s[i].id==x)
                {
                    s[i].num=v;
                    break;
                }
            }
            sort(s+1,s+1+n,cmp); //排序
        }
        else
        {
            int x;
            cin>>x;
            for(int i=1;i<=n;i++) //找到对应位置
            {
                if(s[i].id==x)
                {
                    cout<<i<<endl;
                    break;
                }
            }
        }
    }
    return 0;
}

模拟( $max(Onm,Onlog^n)$73pts)

• 每次调整了以后使用类似插入排序调整数据,每个询问都需要遍历数组。

#include<bits/stdc++.h>
using namespace std;
const int N=8010;
struct Node{
    int num;
    int id;
}s[N];
bool cmp(Node a,Node b) //排序规则
{
    if(a.num<b.num) return true; //数字小的在前面
    if(a.num==b.num&&a.id<b.id) return true; //数字相同，编号小的在前面
    return false;
}
int main()
{
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i].num;
        s[i].id=i;
    }
    sort(s+1,s+n+1,cmp); //排序
    while(q--)
    {
        int op,x,v;
        cin>>op;
        if(op==1)
        {
            cin>>x>>v;
            int k;
            for(int i=1;i<=n;i++) //找到对应位置
            {
                if(s[i].id==x)
                {
                    s[i].num=v;
                    k=i;
                    break;
                }
            }
            while(k>1&&(s[k-1].num>s[k].num||s[k-1].num==s[k].num&&s[k-1].id>s[k].id))
            {
                swap(s[k-1],s[k]);
                k--;
            }
            while(k<n&&(s[k].num>s[k+1].num||s[k].num==s[k+1].num&&s[k].id>s[k+1].id))
            {
                swap(s[k],s[k+1]);
                k++;
            }
        }
        else
        {
            int x;
            cin>>x;
            for(int i=1;i<=n;i++) //找到对应位置
            {
                if(s[i].id==x)
                {
                    cout<<i<<endl;
                    break;
                }
            }
        }
    }
    return 0;
}

模拟(100pts)

• 使用一个新的数组储存原数在排序以后的数组中的位置，这样查询就是$O(1)$了，而且更新的时候也不用查询整个数组寻找位置。

#include<bits/stdc++.h>
using namespace std;
const int N=8010;
struct Node{
    int num;
    int id;
}s[N];
int b[N];
bool cmp(Node a,Node b) //排序规则
{
    if(a.num<b.num) return true; //数字小的在前面
    if(a.num==b.num&&a.id<b.id) return true; //数字相同，编号小的在前面
    return false;
}
int main()
{
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i].num;
        s[i].id=i;
    }
    sort(s+1,s+n+1,cmp); //排序
    for(int i=1;i<=n;i++)
    {
        b[s[i].id]=i;
    }
    while(q--)
    {
        int op,x,v;
        scanf("%d",&op);
        if(op==1)
        {
            cin>>x>>v;
            s[b[x]].num=v;
            int k=b[x];
            //往前移动
            while(k>1&&(s[k-1].num>s[k].num||s[k-1].num==s[k].num&&s[k-1].id>s[k].id))
            {
                swap(s[k-1],s[k]);
                swap(b[s[k-1].id],b[s[k].id]);
                k--;
            }
            //往后移动
            while(k<n&&(s[k].num>s[k+1].num||s[k].num==s[k+1].num&&s[k].id>s[k+1].id))
            {
                swap(s[k],s[k+1]);
                swap(b[s[k].id],b[s[k+1].id]);
                k++;
            }
        }
        else
        {
            int x;
            cin>>x;
            cout<<b[x]<<endl;
        }
    }
    return 0;
}