P10750

035966_L3 · 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 种情况讨论：

由定义得 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;
}