排序

过了十年之后，连当年的评测机在哪里也不知道了。

使用 $k$ 代替题目中的 $R$ 即比赛轮数。

Solution 1：每轮比赛后暴力排序，时间复杂度 $(nk \log n)$。

公元 2024 年的评测机速度完全能接受 $n=10^5,k=50$ 的数据。

用 stable_sort 排序可以把最慢的测试点时间压到 330 毫秒，这得益于归并排序的小常数，也许和这道题目的性质有关，但时间复杂度不会变，单次排序仍然是 $O(n \log n)$。

Solution 2：我是不是提到了归并排序？

容易发现题目本质上是对 $n$ 个数中一半的数加一之后再将序列排序的，也就是说被修改过的数和未被修改过的数形成的子序列都有序，只需要 $O(n)$ 归并两个序列。

时间复杂度 $O(n \log n + nk)$。

#include<bits/stdc++.h>
using namespace std;
struct Player{int i,s;}t1[100'005],t2[100'005],a[200'005];
int n,k,q,w[200'005];
bool cmp(const Player &x,const Player &y){return x.s!=y.s ? x.s>y.s:x.i<y.i;}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k>>q,n*=2;
    for(int i=1;i<=n;i++) cin>>a[i].s,a[i].i=i;
    for(int i=1;i<=n;i++) cin>>w[i];
    stable_sort(a+1,a+n+1,cmp);
    for(int i=1;i<=k;i++){
        for(int j=2;j<=n;j+=2)
            if(w[a[j-1].i]<w[a[j].i]) ++a[j].s,t1[j/2]=a[j-1],t2[j/2]=a[j];
            else ++a[j-1].s,t1[j/2]=a[j],t2[j/2]=a[j-1];
        merge(t1+1,t1+n/2+1,t2+1,t2+n/2+1,a+1,cmp);
    }
    cout<<a[q].i<<'\n';
    return 0;
}