附考场代码

#include<bits/stdc++.h>
using namespace std;
template<class T>inline void read(T &x)
{
	x=0;
	char c=getchar();
	while(!isdigit(c))c=getchar();
	while(isdigit(c))x=x*10+(c&15),c=getchar();
}
#define N 1000001
int n,a[N],cnt,a1[N],a2[N],ans,s1[N<<2],s2[N<<2];
bool bb[N];
inline void update()
{
	int k;
	read(k);
	for(int i=1,x,y;i<=k;i++)read(x),read(y),a[x]=y;
}
inline int max001(int x,int y)
{
	return (a[x]>a[y] || (a[x]==a[y] && x>y))?x:y;
}
inline int min001(int x,int y)
{
	return (a[x]>a[y] || (a[x]==a[y] && x>y))?y:x;
}
inline void build(int p,int l,int r)
{
	if(l==r){s1[p]=s2[p]=l;return;}
	int mid=(l+r)>>1;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
	s1[p]=max001(s1[p<<1],s1[p<<1|1]),s2[p]=min001(s2[p<<1],s2[p<<1|1]);
}
inline void add(int p,int l,int r,int x,bool y)
{
	if(l==r)
	{
		if(y)s1[p]=0,s2[p]=n+1;else s1[p]=s2[p]=l;
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=x)add(p<<1,l,mid,x,y);else add(p<<1|1,mid+1,r,x,y);
	s1[p]=max001(s1[p<<1],s1[p<<1|1]),s2[p]=min001(s2[p<<1],s2[p<<1|1]);
}
inline void solve()
{
	memset(bb,0,sizeof(bb)),ans=0,cnt=0,a[n+1]=2147483647;
	build(1,1,n);
	while(1)
	{
		if(n-cnt==1)break;
		++cnt;
		a1[cnt]=s1[1],a2[cnt]=s2[1];
		bb[a2[cnt]]=1,a[a1[cnt]]-=a[a2[cnt]];
		add(1,1,n,a1[cnt],0),add(1,1,n,a2[cnt],1);
	}
	int las=cnt+1;
	for(int i=cnt;i>=1;i--)
	{
		if(bb[a1[i]])
		{
			for(int j=i;j<las;j++)a[a1[j]]+=a[a2[j]],bb[a2[j]]=0;
			las=i;
		}
	}
	for(int i=1;i<=n;i++)if(!bb[i])++ans;
	printf("%d\n",ans);
}
signed main()
{
	int T;
	read(T),--T;
	read(n);
	for(int i=1;i<=n;i++)read(a[i]);
	solve();
	while(T--)
	{
		update();
		solve();
	}
	return 0;
}