自动搬运

查看原文

来自洛谷，原作者为

	未来姚班zyl 欢迎加入粉丝团！https://www.luogu.com.cn/team/72518|AFO

搬运于2025-08-24 23:07:43，当前版本为作者最后更新于2024-12-27 17:18:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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

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

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

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

• 加入一段数后，先打擂台求出这一段的最小值。
• 与之前剩下的数中可能的最小值放在一起再打一次擂台，求出当前答案 $ans$。
• 把 $ans$ 删除，将 $ans$ 的儿子设为可能的最小值。

设 $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;
}