省队学长给我们拉的模拟赛的 T4，没想到还能交题解，这下不得不写我的第一篇黑题题解来纪念了。

思路

70pts

先引出结论：当最大的蛇吃了后没有变成最小的蛇，它一定会吃；否则需要递推进行决策。

下面解释为什么一定会吃。令初始时蛇的能力为 $A_1,A_2,\dots,A_n$，那么它们一定是单调不降的。若未变成最小的蛇，那么说明 $A_n-A_1\ge A_2$，如果 $n-1$ 不吃，那么游戏结束，$n$ 会吃；否则一定有 $A_{n-1}-A_2\le A_n-A_1$，那么 $n-1$ 一定会死在 $n$ 前面，所以 $n$ 也会吃。

而当最大蛇吃掉后变成了最小蛇，若次大蛇经过一系列头脑风暴后选择不吃，那它就会白吃一回合；否则它不吃。正着决策显然困难，所以选择倒着推回去。

我们可以使用 set 维护这一过程。具体地，先假设所有蛇都不聪明，每条蛇都一定会吃，模拟一轮后可以得到每轮最大的蛇 $eat_i$ 和最小的蛇 $beat_i$。再倒着往前推，定义 $del_i$ 为每条蛇的死亡时间，若 $del_{eat_i}\ge ans$，则说明在它死前游戏就已经结束了，因此可以吃，同时将 $del_{beat_i}$ 设成 $i$；否则不吃，将 $ans$ 更新为 $i$。

100pts

上述做法中瓶颈在于 set 的时间复杂度，我们考虑能否用线性结构进行维护。使用双端队列真是再合适不过了！

具体地，开两个双端队列 $st1,st2$，$st1$ 用来维护未进食过的蛇，$st2$ 维护进食过的蛇。容易发现，除了一种情况外，两个队列一定是具有单调性的。我们先假定两个队列都是队尾最弱，队头最强，下面给出证明：

这一轮进食完毕后的蛇的能力值一定是 $\max(st1_l,st2_l)-\min(st1_r,st2_r)$。分讨一下，发现由于 $max$ 的值一定是单调不升的，因此我们主要对 $min$ 作讨论。记第 $i$ 轮的 $min$ 为 $min_i$，得到以下情况：

• 若 $min_i=st1_r$，那么一定符合单调性：若 $min_{i-1}$ 来自 $st1$，那么一定有 $min_{i-1}\le min_i$，因此此轮能力值一定小于上一轮；若 $min_{i-1}$ 来自 $st2$，那么说明它比 $st1_r$ 后面的那个值大，因此依旧有 $min_{i-1}\le min_i$，于是同理。

• 若 $min_i=st2_r$，那就不一定符合单调性了。如果符合单调性就依旧满足，否则的那种情况会在下面提到。

对于出现不满足单调性的情况，那就只能是当前值比 $st2_r$ 大，即 $st2_r$ 要被吃掉。那么在这种情况下 $st2_r$ 就会选择在上一轮停手。于是你发现这和“剩两条蛇，如果较小的那条能反悔，它一定会反悔”的逻辑是一样的。于是我们就可以从这个时候开始往回推，而不是一定要全部模拟完了。

代码

#include<set>
#include<queue>
#include<iostream>
#define int long long
using namespace std;
const int N=1e6+5;
int _anll_,t;
int n,m,ans,tim,A[N],del[N],eat[N],beat[N];
deque<pair<int,int> > st1,st2;
void solve(bool _anll_){
	if(!_anll_){
		cin>>n;
		for(int i=1;i<=n;i++) cin>>A[i];
	}
	else{
		cin>>m;int a,b;
		while(m--) cin>>a>>b,A[a]=b;
	}
	tim=-1,ans=1;
	while(st1.size()) st1.pop_back();
	while(st2.size()) st2.pop_back();
	for(int i=1;i<=n;i++)
		st1.push_back({A[i],i}),
		eat[i]=beat[i]=del[i]=0;
	for(int i=n;i>1;i--){
		pair<int,int> mx,mn,an;
		if(st1.size()&&st2.size()){
			if(st1.back()>st2.back())
				 {mx=st1.back();st1.pop_back();}
			else {mx=st2.back();st2.pop_back();}
		}
		else if(st1.size())
			 {mx=st1.back();st1.pop_back();}
		else {mx=st2.back();st2.pop_back();}
		if(st1.size()&&st2.size()){
			if(st1.front()<st2.front())
				 {mn=st1.front();st1.pop_front();}
			else {mn=st2.front();st2.pop_front();}
		}
		else if(st1.size())
			 {mn=st1.front();st1.pop_front();}
		else {mn=st2.front();st2.pop_front();}
		beat[i]=mn.second,eat[i]=mx.second;
		an={mx.first-mn.first,mx.second};
		if(st2.size()&&an>st2.front()){
			ans=tim=i;break;
		}
		st2.push_front(an);
	}
	if(tim==-1) tim=2;
	for(int i=tim;i<=n;i++){
		int x=eat[i];
		if(del[x]>=ans) ans=i;
		else del[beat[i]]=i;
	}
	cout<<ans<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>t;
	for(int i=0;i<t;i++) solve(i);
	return 0;
}