题解：P17854 [LBA-OI R6 B] 凌云沐雨

jmxae11 · 2026-11-08 13:50:21 · 题解

设隐藏排列为 A。要求维护一个位置序列 p_1, p_2, \dots, p_{L-1}，满足 A_{p_1} < A_{p_2} < \cdots < A_{p_{L-1}}。

现在考虑把位置 L 接进去：询问 P = (p_1, p_2, \dots, p_{L-1}, L)，设 A_L 在这 L 个数中排第 r 小。

由于前 L-1 个值递增，离散化之后得到的 q 满足 q_i = i（i < r）、q_L = r、q_i = i + 1（r \le i \le L-1）。把它看作映射：1 \sim r-1 各自成一个环，而 r \to r+1 \to \cdots \to L \to r 构成一个环，所以环数恰好是 r。

也就是说，询问返回值就是 A_L 在已有序列里的位置，所以把 L 插到第 r 位，序列仍然保持递增。

从 L = 2 做到 L = n，共 n - 1 次询问。最后 p_1, p_2, \dots, p_n 就是「值第 i 小」的那个位置，令 A_{p_i} = i 还原答案即可。

::::info[code]

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
int n,k;
int ans[maxn];
int id[maxn];
int main(){
    cin>>n>>k;
    id[1]=1;
    for(int len=2;len<=n;len++){
        cout<<"? "<<len;
        for(int i=1;i<len;i++)
            cout<<' '<<id[i];
        cout<<' '<<len<<endl;
        int ret;
        cin>>ret;
        for(int i=len;i>ret;i--)
            id[i]=id[i-1];
        id[ret]=len;
    }
    for(int i=1;i<=n;i++)
        ans[id[i]]=i;
    cout<<"!";
    for(int i=1;i<=n;i++)
        cout<<' '<<ans[i];
    return 0;
}

::::