题解/精简版

e 精简版题解
此题解牺牲运行时间与空间
虽然运行时间直接飚到110ms
但43行代码我个人认为还是比较美观的...吧

#include <bits/stdc++.h>
#define fi first
#define se second
#define Back(x) (q[x].size() ? q[x].back() : null)
#define Front(x) (q[x].size() ? q[x].front() : inf)
using namespace std;
const int N = 1e6 + 7;
int T, n, m, k, c, x, y, a[N];
void solve() {
	deque<pair<int, int> > q[3];
	for (int i = 1; i <= n; ++i) q[1].push_back({a[i], i});
	c = 0, m = 1;
	pair<int, int> x, y, z, null = {-1, -1}, inf = {1e9, 1e9};
	while (q[1].size() + q[2].size() > 2) {
		y = q[1].front(), q[1].pop_front();\
		Back(1) > Back(2) ? (x = Back(1), q[1].pop_back()) : (x = Back(2), q[2].pop_back());
		x.fi -= y.fi;
		if (q[1].empty() || x < q[1].front()) {
			m = q[1].size() + q[2].size() + 2;
			while (q[1].size() + q[2].size() > 1) {
				Back(1) > Back(2) ? (z = Back(1), q[1].pop_back()) : (z = Back(2), q[2].pop_back());
				x = {z.fi - x.fi, z.se};
				if (x > min(Front(1), Front(2))) break;
				++c;
			}
			break;
		} q[2].push_front(x);
	}
	cout << m - (c & 1) << '\n';
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	solve();
	while (--T) {
		cin >> k;
		while (k--) cin >> x >> y, a[x] = y;
		solve();
	} 
	return 0;
}