思路与算法

把实力写成二元组(体力,编号)，按字典序比较。关键引理：当前最强M吃掉最弱m后产生q=M−m，若q不是新状态的最弱蛇，那么这次吃法一定安全。于是先连续执行这些安全吃法。有序原数组用左右指针维护，已经吃过的蛇用一个按实力递减的双端队列维护；从两者的两端即可取全局最强和最弱。第一次得到新的最弱蛇q时，不把它放回队列，而单独保存。接下来最强蛇若吃q，新的蛇如果仍最弱，就继续单独保存；若不再最弱或只剩一蛇，这一步必然安全，链条终止。链中相邻两位的“是否吃”恰好互为否定，因此从首个不确定吃法到终止吃法的步数为奇数时首位吃，否则首位不吃。假设进入这段时有c条蛇，答案为c−(步数模2)。每组修改均作用于原始体力数组，决斗中的扣减只存在队列临时状态。

正确性说明

安全引理证明：M原为最强，m原为最弱。q不是最弱时，后继最强若就是q，它可按生存优先选择，必然活下来；若是另一条R，则R的原实力不超过M，下一条被吃的w体力不少于m。若R不吃，所有蛇都活；若R决定吃，生成r=R−w的体力不大于q，体力相同时R编号小于M编号，所以r严格弱于q。R既然理性选择吃，就必定在后续存活，且其体力只会进一步下降；因此在q获得下一次选择前，始终有一条活着且比q弱的蛇，q不会被吃。引理成立。首次生成最弱蛇之前，历次最弱体力不减、最强实力不增，故相邻生成值的体力不增；体力相等时编号也不增，因此生成队列单调。进入最弱链后只删除原剩余集合的最强者，队列顺序不再受到插入影响。前一位生成的最弱蛇是否死亡，恰等于后一位是否选择吃，所以有限链上的决策逐级取反；终点是已证明安全的吃法或最后一口，奇偶判定准确。前缀全部安全吃法均执行，链首若吃则下一位立即拒绝，因此最终只需c或c−1。

复杂度

每组数据的原数组初始化/读入O(n)，生成队列缓冲区只分配一次O(n)。每次实际模拟都使剩余集合减少一条蛇，且每条蛇至多入队一次、两端弹出一次；安全前缀和最弱链合计O(n)时间。T组总时间O(Tn+Σk)，读取初始数组O(n)、更新每项O(1)，均已计入。数组和队列共O(n)空间；无需平衡树或对每组重新排序。

易错点

实力相同必须用较大编号判为较强，不能只比较体力。体力为0时也可吃，最强蛇体力不减并可持续获益。双队列的生成值单调性只在首次生成最弱蛇之前成立；进入最弱链后若仍盲目插入，等值编号会破坏顺序。后续输入相对于上一组的原始体力修改，不是上一轮决斗后的体力；同一位置多次修改以最后一次为准。仅最终修改后的数组保证不降序，不应自行重排蛇的编号。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct FastInput {
    static const int SZ = 1 << 16;
    char data[SZ];
    int at = 0, length = 0;
    int get() {
        if (at == length) {
            length = fread(data, 1, SZ, stdin);
            at = 0;
            if (!length)
                return -1;
        }
        return data[at++];
    }
    int number() {
        int c;
        do {
            c = get();
        } while (c <= ' ' && c >= 0);
        int x = 0;
        while (c >= '0' && c <= '9') {
            x = x * 10 + c - '0';
            c = get();
        }
        return x;
    }
};
struct Duel {
    const vector<int> &a;
    vector<unsigned long long> &generated;
    int left, right, head, tail;
    Duel(const vector<int> &input, vector<unsigned long long> &buffer)
        : a(input), generated(buffer), left(0), right((int)input.size() - 1), head(0), tail(-1) {
    }
    unsigned long long original(int i) {
        return (static_cast<unsigned long long>(a[i]) << 20) | i;
    }
    unsigned long long minimum() {
        if (left > right)
            return generated[tail];
        if (head > tail)
            return original(left);
        return min(original(left), generated[tail]);
    }
    unsigned long long popMin() {
        if (left > right || (head <= tail && generated[tail] < original(left)))
            return generated[tail--];
        return original(left++);
    }
    unsigned long long popMax() {
        if (left > right || (head <= tail && generated[head] > original(right)))
            return generated[head++];
        return original(right--);
    }
    int solve() {
        int alive = (int)a.size();
        while (alive > 1) {
            auto low = popMin(), high = popMax();
            auto changed = high - ((low >> 20) << 20);
            if (alive == 2)
                return 1;
            if (changed >= minimum()) {
                // Before the first newly weakest snake, generated keys are nonincreasing.
                assert(head > tail || generated[tail] >= changed);
                generated[++tail] = changed;
                --alive;
                continue;
            }
            // Hold the newly weakest snake outside both deques. No insertion in this phase.
            int remaining = alive - 2, parity = 1;
            do {
                high = popMax();
                changed = high - ((changed >> 20) << 20);
                --remaining;
                parity ^= 1;
                if (!remaining || changed >= minimum())
                    break;
            } while (true);
            return alive - parity;
        }
        return 1;
    }
};
int main() {
    FastInput in;
    int T = in.number(), n = in.number();
    vector<int> a(n);
    for (int &x : a)
        x = in.number();
    vector<unsigned long long> generated(n);
    printf("%d\n", Duel(a, generated).solve());
    while (--T) {
        int k = in.number();
        while (k--) {
            int index = in.number() - 1, value = in.number();
            a[index] = value;
        }
        printf("%d\n", Duel(a, generated).solve());
    }
}