自动搬运

查看原文

来自洛谷，原作者为

	itisover 招募ACM队友

搬运于2025-08-24 22:51:09，当前版本为作者最后更新于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;
}