专栏文章

题解：AT_kupc2020_j Median Query

sshinzAnmonoszm 妹妹
AT_kupc2020_j题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miozlmhe
此快照首次捕获于
2025/12/03 03:44
3 个月前
此快照最后确认于
2025/12/03 03:44
3 个月前
查看原文
考虑 n=4n=4 时怎么做。两两之间询问必能得到大小位于中间的两个数，然后相同的数判一下大小即可。
如果 n>4n>4，我们设上面找出来的两个数为 L,RL,R，且 L>RL>R。那么同一时刻序列中一定只有两个数 =L=L，也只有两个数 =R=R。
设当前 =L=L 的数为 a,ba,b，=R=R 的数为 c,dc,d，加入的数为 ii，答案序列为 pip_i。则对 a,c,ia,c,i 进行询问，答案为 KK。若 L<K<RL<K<R 则直接令 pi=Kp_i=K。否则对 L,RL,R 进行更新，具体地，询问 b,d,ib,d,i，答案为 QQ。不妨假设 K≤LK\leq L（k≥Rk\geq R 同理即可）则说明 a,ba,b 中一定有一个数 =L=L，我们判断是哪个即可。如果 K>QK>Q，即 max⁡(a,i)>max⁡(b,i)\max(a,i)>\max(b,i)，则 pa=Lp_a=L，否则 pb=Lp_b=L。一定不要忘记更新 LL 和 RR。
最后我们把相同的数判一下大小即可，询问次数上界不超过 2n2n。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...