题解：[COCI 2024/2025 #3] 处理器 / Procesor

· · 题解

我们可以用 n-1 次操作得出 n 个数当中的最小值，使用任意一种打擂台的方式即可。

然而这题还要求出类似次小值、第三小值等等，所以我们需要保留比较过程中的信息。

大小关系常常用图论描述，如果 a_i 大于 a_j，我们就连边 i\rightarrow j，在一次打擂台之后，我们将连出一颗外向树，即边都指向自己的儿子。

先不管打擂台的顺序和方式是怎样的，我们先整理本题的思路：

设 m=\sum x_i，我们分析这个思路的操作次数：

第一步是 O(m) 次操作。

第三步带来的候选点的总数是 O(m) 的，第二步中打 n 次擂台，操作数是 O(nm) 的。

打擂台的过程无法优化，我们只能尝试减少第三步带来的候选点数。在树上这体现为 deg_{ans}。

我们采用类似线段树的结构进行打擂台，求出左区间和右区间的最小值，再将它们放一起打擂台。

这样每个点只会进行 O(\log m) 次比较，其度数就为 O(\log m)，总操作次数变为 O(m+n\log m) 轻松通过此题。

#include<bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define repn(x) rep(x,1,n)
#define pb push_back
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57) {if(c=='-') w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-48,c=getchar();return s*w;}
using namespace std;
const int N=3e5+5;
int n,a[N],pr[N];
inline int cmp(int a,int b){
    cout <<"? "<<a<<' '<<b<<endl;
    return read();
}
int deg[N];
map<int,int>Nw;
vector<int>p[N];
inline int solve(int l,int r){
    if(l==r)return l;
    int a=solve(l,mid),b=solve(mid+1,r);
    if(cmp(a,b))return p[b].pb(a),b;
    return p[a].pb(b),a;
}
int st[N],tp;
inline int Sol(int l,int r){
    if(l==r)return st[l];
    int a=Sol(l,mid),b=Sol(mid+1,r);
    if(cmp(a,b))return p[b].pb(a),b;
    return p[a].pb(b),a;
}
inline void Solve(){
    tp=0;
    for(auto x:Nw)st[++tp]=x.first;
    int now=Sol(1,tp);
    Nw.clear();
    for(auto y:p[now])Nw[y]=1;
    cout <<"! "<<now<<endl;
}
inline void Main(){
    n=read();
    repn(i){
        a[i]=read(),pr[i]=pr[i-1]+a[i];
        int l=pr[i-1]+1,r=pr[i];
        Nw[solve(l,r)]=1;
        Solve();
    }
}
signed main(){
    int T=1;
    while(T--)Main();
    return 0;
}