自动搬运

查看原文

来自洛谷，原作者为

	MoSalah 退役不退学

搬运于2025-08-24 22:37:58，当前版本为作者最后更新于2022-05-02 22:53:36，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意

这是一道交互题

首先，在这里感谢出题人让我知道了怎么写交互题。

在 $5500$ 次询问内，你要求出最初的 $a$ 数组。

询问方式有三种：

• $\texttt{? 1 i}$ 询问 $d_{1 \sim i}$ 中有几个不同的值，交互库会返回一个正整数 $x$ 表示答案。

• $\texttt{? 2 i}$ 使 $a_i=0$。

• $\texttt{! a1 a2 a3 ... an}$ 输出答案。

返回的数值 $x$ 就是 $d_i = \max \limits_{j=1}^{i} \left \{a_j \right \}$

题解

模拟？$30$ 分。

$a$ 数组中每一位往前的最大值就可能是：

$a_1,a_2,a_3,...,a_{i-1},n,n,n,n,n,n,n...$

画图发现，如果第 $i$ 位的值为当前数组中最大值，那么询问这个点往后的询问值一定与第 $i$ 位的询问值相符。那么最后一位的询问值一定与第 $i$ 位的询问值一样。现在就是要找到这个 $i$ 位，记录下来。

考虑二分。

在这个数组中二分查询这个 $i$ 位，首先询问一次 $n$ 位，如果第 $j$ 位和第 $n$ 位相同，那么查找 $j$ 往前的位置，不然查找 $j$ 往后的位置，最终查找到开头的位置，那么这位置一定是 $n$。标记后将 $a_i$ 清零，那么这个序列中的最大值就是 $n-1$，重复操作，直到确定 $1$ 的位置。

过程在图片里面。

清零之后求 $n-1 , n-2 , n-3 , ... , 1$ 以此类推。好了，这道题就解决了。

代码

#include <bits/stdc++.h>
using namespace std;
int ans[50005];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        for(int i=n;i>=1;i--){
            printf("? 1 %d\n\n",n);
            fflush(stdout);//刷新缓存
            int biao;
            scanf("%d",&biao);
            int l=1,r=n;
            while(l<r){
                int mid=(l+r)>>1;
                int tmp;
                printf("? 1 %d\n\n",mid);
                fflush(stdout);//刷新缓存
                scanf("%d",&tmp);
                if(tmp==biao) r=mid;
                else l=mid+1;
            }
            printf("? 2 %d\n\n",r);
            fflush(stdout);//刷新缓存
            ans[r]=i;
        }
        printf("!");
        for(int i=1;i<=n;i++) printf(" %d",ans[i]);
        puts("\n");
        fflush(stdout);//刷新缓存
    }
    return 0;
}