题解：P9721 [EC Final 2022] Inversion

itisover · 2024-11-12 17:25:01 · 题解

新教练布置的题，挺有意思的。我的做法不太用预处理很多，常数挺小的，没人写过就写个题解。

首先考虑 i-1 到 i 的过程，本质上是要在原先确定好顺序的前 1 \sim i-1 项中插入第 i 项，即确定 i 在前 i-1 中是第几小。

很容易想到从第一小开始依次比较，但是至少 n^2 问询，无法接受。于是想到可以二分找第 k 小，得到了 n \log_2 n 的做法。

问题来了，怎么通过题设交互方法实现任意位置 i,j (i<j) 两数的大小比较？

• 两数在序列中相邻：? i j 返回的就是 i>j 是真是假。
• 两数不相邻：我有一个不一样的思路：

  首先询问 ? i j 和 ? i+1 j 记结果为 q1,q2

  显然 q1 即为 (q2 + \sum\limits^{j}_{k=i+1} [p_i>p_k] )\mod 2 = (q2 + \sum\limits^{j-1}_{k=i+1} [p_i>p_k] + [p_i>p_j])\mod 2

  意思是 i\sim j 的逆序对个数，等于 i+1 \sim j 的逆序对个数，再加上 i+1 \sim j 中比第 i 项小的个数

  我们可以维护一个 sum[i]，表示第 i 项到当前循环处理到的最后一项之间，有几个是小于第 i 项的。维护就是：每加入一个数，只用把比他大的所有数的 sum[i] 增加 1 即可。

  所以只需判断 (q2 + sum[i]) % 2 与 q1 的奇偶性是否发生了变化即可判断 [p_i > p_j] 是否为真。

至此，题目迎刃而解，感觉思路还是挺自然的，不会很复杂，实现也挺简单，很小清新的题。

#include<bits/stdc++.h>
using namespace std;
const int _=2005;
int n;
int sum[_],rk[_],id[_];
int main(){
    cin>>n;
    rk[1]=1;
    for(int i=2;i<=n;++i){
        int l=1,r=i-1,ans=0;
        while(l<=r){
            int mid=(l+r)>>1;
            int q1,q2;
            cout<<"? "<<rk[mid]<<" "<<i<<endl;
            cin>>q1;
            if(rk[mid]==i-1){
                if(q1) r=mid-1;
                else ans=mid,l=mid+1;
            }
            else{
                cout<<"? "<<rk[mid]+1<<" "<<i<<endl;
                cin>>q2;
                if((q2+sum[rk[mid]])%2==q1) ans=mid,l=mid+1;
                else r=mid-1;
            }
        }
        for(int j=i;j>ans+1;--j) rk[j]=rk[j-1];
        rk[ans+1]=i;
        for(int j=ans+2;j<=i;++j) ++sum[rk[j]];
    }
    for(int i=1;i<=n;++i) id[rk[i]]=i;
    cout<<"! ";
    for(int i=1;i<=n;++i) cout<<id[i]<<" ";
    cout<<endl;
    return 0;
}