题解：AT_kupc2020_j Median Query

shinzAnmono · 2025-07-04 11:38:16 · 题解

考虑 n=4 时怎么做。两两之间询问必能得到大小位于中间的两个数，然后相同的数判一下大小即可。

如果 n>4，我们设上面找出来的两个数为 L,R，且 L>R。那么同一时刻序列中一定只有两个数 =L，也只有两个数 =R。

设当前 =L 的数为 a,b，=R 的数为 c,d，加入的数为 i，答案序列为 p_i。则对 a,c,i 进行询问，答案为 K。若 L<K<R 则直接令 p_i=K。否则对 L,R 进行更新，具体地，询问 b,d,i，答案为 Q。不妨假设 K\leq L（k\geq R 同理即可）则说明 a,b 中一定有一个数 =L，我们判断是哪个即可。如果 K>Q，即 \max(a,i)>\max(b,i)，则 p_a=L，否则 p_b=L。一定不要忘记更新 L 和 R。

最后我们把相同的数判一下大小即可，询问次数上界不超过 2n。

#include<iostream>
#include<algorithm>
#include<vector>
const int sz=6e4+10;
bool query1(int i,int j){
  std::cout<<"? 2 "<<i<<" "<<j<<std::endl;
  int res;
  std::cin>>res;
  return res==i;
}
int query2(int i,int j,int k){
  std::cout<<"? 1 "<<i<<" "<<j<<" "<<k<<std::endl;
  int res;
  std::cin>>res;
  return res;
}
int p[sz];
void solve(int N){
  int A=query2(1,2,3),B=query2(1,2,4),C=query2(1,3,4),D=query2(2,3,4),L,R,a,b,c,d;
  if(A==B)p[a=1]=p[b=2]=L=A,p[c=3]=p[d=4]=R=C;
  if(A==C)p[a=1]=p[b=3]=L=A,p[c=2]=p[d=4]=R=B;
  if(A==D)p[a=2]=p[b=3]=L=A,p[c=1]=p[d=4]=R=C;
  if(L>R)std::swap(L,R),std::swap(a,c),std::swap(b,d);
  for(int i=5;i<=N;i++){
    int k=query2(a,c,i);
    if(k>L&&k<R)p[i]=k;
    if(k<=L){
      int q=query2(b,d,i);
      if(k<q)p[b]=L,b=i,p[a]=p[i]=L=k;
      else p[a]=L,a=i,p[b]=p[i]=L=q;
    }
    if(k>=R){
      int q=query2(b,d,i);
      if(k>q)p[d]=R,d=i,p[c]=p[i]=R=k;
      else p[c]=R,c=i,p[d]=p[i]=R=q;
    }
  }
  (query1(a,b)?p[a]:p[b])=1,(query1(c,d)?p[d]:p[c])=N;
  std::cout<<"! ";
  for(int i=1;i<=N;i++)std::cout<<p[i]<<" ";
  std::cout<<std::endl;
}
int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  std::cin>>n,solve(n);
  return 0;
}