自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 23:00:53，当前版本为作者最后更新于2024-11-17 00:21:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

设 $N = 1000$。给定一个 $1 \sim N$ 的排列 $p$，你在每次交互中询问一个区间 $[a,b]$，可以得到 $p_a \sim p_b$ 中逆序对的数量对 $2$ 取模的值。请在若干次交互后确定排列 $p$。

交互次数上限：$Q_{30}=5 \times 10^5$（$30$ 分），$Q_{100}=4 \times 10^4$（$100$ 分）。

双倍经验：P9721。

推销相关文章！

很明显，如果我们可以在可接受的询问次数内比较任意两项 $p_x,p_y$ 的值（即实现一个 cmp 函数），那么这不就是就是一个赤裸裸的 AT_practice_2 Subtask #2（交互式排序）吗！

实际上，这个 cmp 函数可以用 $4$ 次询问实现：

设 $s_{i,j}=0/1$ 表示 $(p_i,p_j)$ 是否是逆序对：若 $s_{i,j}=1$，则 $p_i>p_j$，否则 $p_i<p_j$。

设 $t_{i,j}$ 是 $p_i \sim p_j$ 中逆序对的数量。对每个逆序对 $(p_x,p_y)$ 分 $4$ 种情况讨论：

• $x \ne i,y \ne j$ 情况下逆序对的个数：$A=t_{i+1,j-1}$；
• $x = i,y \ne j$ 情况下逆序对的个数：$B=t_{i,j-1}-A$；
• $x \ne i,y = j$ 情况下逆序对的个数：$C=t_{i+1,j}-A$；
• $x = i,y = j$ 情况下逆序对的个数：$D=t_{i,j}-A-B-C$。

由定义得 $D=s_{i,j}$，然后整理上面 $4$ 个式子：

$$s_{i,j}=t_{i,j}-t_{i,j-1}-t_{i-1,j}+t_{i-1,j-1}$$

通过询问 ? i j，我们可以得到 $t_{i,j}\!\mod 2$ 的值。因此，我们可以在 $4$ 次询问内得到 $s_{i,j} \!\mod 2$ 的值（实际上就是 $s_{i,j}$ 的值，因为 $s_{i,j}$ 只能取 $0$ 或 $1$）。

综上，我们用 $4$ 次询问实现了 cmp 函数。

套上 $O(N \log N)$ 的排序（比如归并排序）模板后，我们得到了一个总共需要 $4N \log N=4 \times 10^4$ 次询问的 $O(N \log N)$ 解法，刚好能过！

（看来出题人在询问次数上卡了常数，差评！）

特别提醒：这题卡了 STL sort，用它只能得到 $52$ 分！

使用了 $27331$ 次询问的 AC Code（实际上它是 $O(N \log ^2 N)$ 的）：

#include <bits/stdc++.h>
using namespace std;
int a[1012],b[1012];
map<pair<int,int>,bool> p;
bool check(int x,int y)
{
    if(p.count(make_pair(x,y))) return p[make_pair(x,y)];
    // 若之前进行过完全相同的询问，直接调用之前的询问结果
    cout<<"? "<<x<<' '<<y<<endl;
    bool sw;
    cin>>sw;
    p[make_pair(x,y)]=sw;
    return sw;
}
bool cmp(int x,int y)
{
    bool sw=true;
    if(x>y) sw=false;
    if(x>y) swap(x,y);
    sw^=check(x,y);
    if(y-x>1) sw^=check(x,y-1);
    if(y-x>1) sw^=check(x+1,y);
    if(y-x>2) sw^=check(x+1,y-1);
    // x = y 时答案显然是 0，就不用询问了
    return sw;
}
void st(int l,int r)
{
    // 归并排序
    if(l==r) return;
    int lmid=(l+r)/2,rmid=lmid+1;
    st(l,lmid),st(rmid,r);
    int tmp[1012]={0};
    int p1=l,p2=rmid,p3=l;
    while(p1!=rmid&&p2!=r+1)
    {
        if(cmp(a[p1],a[p2])) tmp[p3]=a[p1],p1++,p3++;
        else tmp[p3]=a[p2],p2++,p3++;
    }
    while(p1<rmid) tmp[p3]=a[p1],p1++,p3++;
    while(p2<r+1) tmp[p3]=a[p2],p2++,p3++;
    for(int i=l;i<=r;i++)
        a[i]=tmp[i];
}
int main()
{
    for(int i=1;i<=1000;i++)
        a[i]=i;
    st(1,1000);
    
    cout<<"! ";
    for(int i=1;i<=1000;i++)
        b[a[i]]=i;
    // 排序得到的结果是“1, 2, 3, ... 分别出现在哪个位置”，因此需要转换
    for(int i=1;i<=1000;i++)
        cout<<b[i]<<' ';
    cout<<endl;
    return 0;
}