时间较小 75ms

s2

s

s1

#include<bits/stdc++.h>
using namespace std;
namespace FGF{
	int n,m;
	const int N=1e6+5;
	int b[N],a[N],q[N],de[N],h,t,st,ed,fl,end;
	struct Node{
		int mx,mi;
		Node(){};
		Node(int _mx,int _mi):mx(_mx),mi(_mi){};
	}c[N];
	int read(){
		int s=0;char ch=getchar();
		while(!isdigit(ch))ch=getchar();
		while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
		return s;
	}
	inline int getcm(){
		int mi;
		if(st>ed)mi=q[t];
		else if(h>t)mi=st;
		else if(a[st]<a[q[t]]||(a[st]==a[q[t]]&&st<q[t]))mi=st;
		else mi=q[t];
		return mi;
	}
	inline int getmi(){
		int mi;
		if(st>ed)mi=q[t],t--;
		else if(h>t)mi=st,st++;
		else if(a[st]<a[q[t]]||(a[st]==a[q[t]]&&st<q[t]))mi=st,st++;
		else mi=q[t],t--;
		return mi;
	}
	inline int getmx(){
		int mx;
		if(st>ed)mx=q[h],h++;
		else if(h>t)mx=ed,ed--;
		else if(a[ed]>a[q[h]]||(a[ed]==a[q[h]]&&ed>q[h]))mx=ed,ed--;
		else mx=q[h],h++;
		return mx;
	}
	void solve(){
		h=1,t=0,st=1,ed=n,fl=0,end=n-1;
		for(int i=1;i<n;i++){
			int mx=getmx(),mi=getmi(),cm=getcm();
			a[mx]-=a[mi];
			q[++t]=mx;
			c[i].mx=mx,c[i].mi=mi;
			if(a[mx]>a[cm]||(a[mx]==a[cm]&&mx>cm)){
				if(fl){
					end=i;
					break;
				}
			}
			else fl=i; 
		}
		for(int i=1;i<=n;i++) de[i]=end+1;
		de[c[end].mi]=end;
		int ans=end+1;
		for(int i=end-1;i;i--){
			if(de[c[i].mx]<ans)ans=i;
			de[c[i].mi]=i;
		}
		printf("%d\n",n-ans+1);
	}
	void work(){
		int T=read();n=read();
		for(int i=1;i<=n;i++)
			b[i]=a[i]=read();
		solve();
		for(int i=2;i<=T;i++){
			int k=read();
			for(int j=1;j<=n;j++)a[j]=b[j];
			for(int j=1;j<=k;j++){
				int x=read(),y=read();
				b[x]=a[x]=y;
			}
			solve();
		}
	}
}
int main(){
	FGF::work();
	return 0;
}