首先是一个观察：由于蛇很智慧，所以如果能轮到它决策，它就绝对不会死，因为如果它预料到它会死它就会直接选择结束。
分讨一条蛇吃完后的情况：
- 如果这条蛇吃完之后还是最强的，那么肯定会吃
- 如果不是最强的也不是最弱的，那么下一轮是次强的决策，且这时候最弱的变为了原先次弱的，所以如果次强蛇吃了，次强蛇就会比最强蛇小，如果最强蛇死了，那么次强蛇必定先死，由于次强蛇能够决策，所以它肯定不会死，所以最强蛇也不会死。
- 是最弱的。那么假设现在开始每条决策的蛇是 \(1, 2, 3, \cdots, k\), 如果 \(1\) 吃了之后变成了最弱的，由 \(2\) 决策，如果 \(2\) 吃了 \(1\) 不是最弱的，那根据第二点，\(1\) 会死，\(1\) 知道这点，不会吃。否则，\(2\) 需要看 \(3\) 来决定吃不吃，如果 \(2\) 会吃 \(1\)，\(1\) 就会选择结束，否则 \(1\) 会吃，对于 \(2\) 也同理，同时 \(3\) 需要依赖 \(4\), 以此类推，如果只剩两条蛇了，那么当前决策的蛇肯定不敢吃，不然会被最后一条吃掉，所以我们发现如果 \(k\) 是奇数就会吃。并且吃了之后 \(2\) 也不会吃了，因为 \(2\) 变成了新的 \(1\), \(k\) 变成了偶数，所以一旦出现这种情况，最多再吃一次了。
这样可以直接 set 维护最大值和最小值，时间复杂度 \(\mathcal{O}(Tn \log n)\)。
考虑经典 trick 把队列当优先队列做，需要满足每次入队的点有单调性，首先一开始的蛇本身有单调性，其次根据第二点的观察，如果一条蛇吃了，那肯定会比上一条吃了的蛇弱，所以再开一个队列维护吃过的蛇，每次入队即可。
时间复杂度 \(\mathcal{O}(Tn)\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 i128;
typedef pair<int, int> pii;
const int N = 1e6 + 10, mod = 998244353;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {cout << arg << ' ';dbg(args...);
}
int T, n, a[N];
int main() {// freopen("data.in", "r", stdin);// freopen("data.out", "w", stdout);ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> T >> n;for (int tc = 1; tc <= T; tc++) {if (tc == 1) for (int i = 1; i <= n; i++) cin >> a[i];else {int k, x, y; cin >> k;while (k--) { cin >> x >> y; a[x] = y; }}deque<pii>q1, q2;for (int i = 1; i <= n; i++) q1.push_back({a[i], i});int ans;while (1) {if (q1.size() + q2.size() == 2) {ans = 1;break;}int x, y, id; y = q1.front().first; q1.pop_front();if (q2.empty() || (!q1.empty() && q1.back() > q2.back())) { tie(x, id) = q1.back(); q1.pop_back(); } else { tie(x, id) = q2.back(); q2.pop_back(); }pii now = {x - y, id};if (q1.empty() || q1.front() > now) {ans = q1.size() + q2.size() + 2; int cnt = 0;while (1) {cnt ^= 1;if (q1.size() + q2.size() == 1) { if (!cnt) ans--; break; }if (q2.empty() || (!q1.empty() && q1.back() > q2.back())) { tie(x, id) = q1.back(); q1.pop_back(); } else { tie(x, id) = q2.back(); q2.pop_back(); }now = {x - now.first, id};if ((q1.empty() || now < q1.front()) && (q2.empty() || now < q2.front())) continue;if (!cnt) ans--;break;}break;} else q2.push_front(now);}cout << ans << '\n';}return 0;
}