自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 22:59:52，当前版本为作者最后更新于2024-06-22 18:35:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

考虑对于每个元素单独计算排名。假设我们现在要求 $x$ 在 $P$ 中的排名（设该排名为 $y$），可以考虑如下的询问构造：

• $R_1=\{x,\ldots\}$
• $R_2=\{\ldots,x\}$

其中两者 $\ldots$ 的部分需要是一样的；设 $\ldots$ 内部的贡献为 $\Delta$，即与 $x$ 无关的贡献。

根据题意，可以得出 $\mathrm{answer}(R_1)=y+\Delta$，$\mathrm{answer}(R_2)=N-y-1+\Delta$，于是 $y=\dfrac{\mathrm{answer}(R_1)-\mathrm{answer}(R_2)+N-1}{2}$。直接按这种方法对于每个元素构造两个排列可以做到 $2N$ 次询问，可获得 $70$ 分。

考虑压缩询问次数，即考虑合并一些元素的询问：观察到 $R_2$ 为 $R_1$ 向左循环位移一位得到的结果，于是令初始排列为 $\{1,2,\ldots,N\}$，每次将其向左循环位移一位继续询问，即可依次得出元素 $1,2,\ldots,N$ 的排名。

放代码（代码中的数组均为 $0$-indexed）：

#include<bits/stdc++.h>
using namespace std;
void answer(vector<int>);
int publish(vector<int>);
void solve(int n){
  vector<int> a(n),r(n);
  for(int i=0;i<n;i++){
    vector<int> v;
    for(int j=i;j<n;j++)
      v.emplace_back(j+1);
    for(int j=0;j<i;j++)
      v.emplace_back(j+1);
    a[i]=publish(v);
  } // 循环位移构造询问
  for(int i=0;i<n;i++)
    r[a[i]-a[(i+1)%n]+n-1>>1]=i+1;
    // 计算排名并存入答案
  answer(r);
}