题解

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long int_;
inline int readint(){
	int a = 0; char c = getchar(), f = 1;
	for(; c<'0'||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}
inline void writeint(int_ x){
	if(x > 9) writeint(x/10);
	putchar((x-x/10*10)^48);
}

const int MaxN = 1000005;
int a[MaxN], n, b[MaxN];
bool cmp(const int &x,const int &y){
	return a[x] < a[y] || (a[x] == a[y] && x < y);
}

deque<int> one, two;
bool alive(){
	int x = one.back(); one.pop_back();
	if(one.empty()) return true;
	a[x] -= a[one.front()];
	one.pop_front();
	if(!one.empty() && cmp(one.front(),x))
		return false; // always able to eat
	one.push_front(x); return !alive();
}
void merge_(){
	deque<int> res; res.clear();
	while(!one.empty() || !two.empty())
		if(two.empty() || (!one.empty() && cmp(one.front(),two.front())))
			res.push_back(one.front()), one.pop_front();
		else res.push_back(two.front()), two.pop_front();
	one.swap(res);
}
int solve(){
	one.clear(), two.clear();
	for(int i=1; i<=n; ++i)
		a[i] = b[i], one.push_back(i);
	while(two.size()+one.size() > 1u){
		deque<int> *tiny = &one, *big = &one;
		if(!two.empty() && cmp(one.back(),two.back()))
			big = &two; // where's max
		if(!two.empty() && cmp(two.front(),one.front()))
			tiny = &two; // where's min
		int x = (*big).back();
		a[x] -= a[(*tiny).front()]; // eat it
		(*big).pop_back(), (*tiny).pop_front();
		if(one.empty()) one.swap(two); // reset
		two.push_front(x); // minimum one
		if(!one.empty() && cmp(x,one.front()))
			break;
	}
	if(one.size()+two.size() == 1u)
		return 1; 
	merge_(); int ans = one.size();
	if(!alive()) ++ ans;
	return ans;
}

int main(){
	int T = readint();
	n = readint();
	rep(i,1,n) b[i] = readint();
	printf("%d\n",solve());
	for(int i=2; i<=T; ++i){
		int k = readint();
		for(int x; k; --k){
			x = readint();
			b[x] = readint();
		}
		printf("%d\n",solve());
	}
	return 0;
}