代码（附评测记录）

#include<iostream>
#include<deque>
using namespace std;
const int maxn=1e6+5;
int t,n,a[maxn],k;
bool cmp(pair<int,int>x,pair<int,int>y)
{
	if(x.first!=y.first)return x.first>y.first;
	return x.second>y.second;
}
int main()
{
	cin>>t;
	cin>>n;
	for(int _=1;_<=t;++_)
	{
		int ans=0,end=0;
		if(_==1)
			for(int i=1;i<=n;++i)cin>>a[i];
		else
		{
			cin>>k;
			int x,y;
			for(int i=1;i<=k;++i){cin>>x>>y;a[x]=y;}
		}
		deque<pair<int,int> >q1,q2;//头强，尾弱 
		for(int i=1;i<=n;++i)
			q1.push_front({a[i],i});
		bool o2=1;
		int strong,ids,weak,idw;
		while(1)//first state
		{
			if(q1.size()+q2.size()==2)
				ans=n-1,o2=0;
			weak=q1.back().first;idw=q1.back().second;
			q1.pop_back();
			if(q2.empty()||q1.empty()==0&&cmp(q1.front(),q2.front()))
				strong=q1.front().first,ids=q1.front().second,q1.pop_front();
			else strong=q2.front().first,ids=q2.front().second,q2.pop_front();
			int noww=0x7fffffff,idn=0x7fffffff;
			if(q1.empty()==0) noww=q1.back().first,idn=q1.back().second;
			if(q2.empty()==0&&q2.back().first<=noww) noww=q2.back().first,idn= q2.back().first==noww? min(idn,q2.back().second):q2.back().second;            
//			cout<<noww<<' '<<idn<<endl;
			if(strong-weak<noww||strong-weak==noww&&ids<idn)
				{++end;break;}
			q2.push_back({strong-weak,ids});
			++ans;
		}
//        cout<<endl;
		while(o2)//second state
		{
			if(q1.size()+q2.size()+1==2)
				{break;}
			weak=strong-weak;idw=ids;
//			q1.pop_back();
			if(q2.empty()||q1.empty()==0&&cmp(q1.front(),q2.front()))
				strong=q1.front().first,ids=q1.front().second,q1.pop_front();
			else strong=q2.front().first,ids=q2.front().second,q2.pop_front();
			int noww=0x7fffffff,idn=0x7fffffff;
			if(q1.empty()==0) noww=q1.back().first,idn=q1.back().second;
			if(q2.empty()==0&&q2.back().first<=noww) noww=q2.back().first,idn= q2.back().first==noww? min(idn,q2.back().second):q2.back().second;
//			cout<<noww<<' '<<idn<<endl;
//			q2.push_back({strong-weak,ids})
			if(strong-weak>noww||strong-weak==noww&&ids>idn)
				{break;}
			++end;
		}
		if(end!=0&&end%2==0)ans++;
		cout<<n-ans<<"\n";
	}
}

评测记录