CF1521C Nastia and a Hidden Permutation

真是个沙比提,比赛的时候也想出来了,但是因为太迷糊了没写完

首先我们先考虑如何确定下最大值所在的位置。

执行询问$max(min(n-1,p_i),min(n,p_{i+1}))$,这个询问实际上等价于$max(min(n-1,p_i),p_{i+1})$。

  • 如果结果是n,那么说明$p_{i+1}=n$(很显然,max里第一项不会超过n-1)。
  • 如果结果比n-1要小,那么说明$p_i$和$p_{i+1}$都不是n。
  • 如果结果是n-1,那么就要讨论下了。这个时候n可能出现在这两个数里,也可能没出现。

我们再构造另一个询问:$min(max(n-1,p_i),max(n,p_{i+1}))$,显然这个询问等价于$max(n-1,p_i)$,所以我们可以利用这个询问来检查$p_i$的值是不是n。

在找到最大值的位置,设它为$maxpos$,那么我们对于每一个$i\neq maxpos$,构造询问$min(max(1,p_i),max(2,p_{maxpos}))$,这个询问等价于$p_i$,然后就可以求出来每个位置的值了。

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据