题解：[Algo Beat Contest 002 B] Bicycle Competition

· · 题解

题面展示

自行车比赛中有 N 位选手，每位选手当前的排名为 A_i。比赛中有 Q 个事件发生：

1 x：编号为 x 的选手超过了前面一位选手。如果该选手此时已经是第一名，则忽略该操作。

2 x：询问排名为 x 的选手编号。

3 x：询问编号为 x 的选手排名。

解题思路

考虑维护排名为 i 的选手编号 P_i。

在修改操作时，如 A_x = 1，什么都不用改，我们在接下来的推导中假设 A_x > 1。注意到可以 O(1) 得到给出编号的选手前面那位选手的编号，那就是 P_{A_x-1}。

那么直接交换一下，然后更新两名选手的排名。

查询随便查。

代码展示

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[200005],p[200005];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,q;
    cin>>n>>q;
    for (int i=1;i<=n;i++)cin>>a[i],p[a[i]]=i;
    while (q--){
        int op,x;
        cin>>op>>x;
        if (op==1){
            if (a[x]==1)continue;
            int rnk=a[x];
            swap(p[rnk],p[rnk-1]);
            a[p[rnk]]=rnk;
            a[p[rnk-1]]=rnk-1;
        }
        else if (op==2){
            cout<<p[x]<<"\n";
        }
        else{
            cout<<a[x]<<"\n";
        }
    }
    return 0;
}