调了很久，根本没有头绪

#include <cassert>
#include <cstdio>
#include <cstring>
#include <deque>

using namespace std;
typedef unsigned long long u64;

const int maxn = 1000001;

struct snake {
    int id;
    u64 power;
    bool operator<(const snake& rhs) const {
        return power == rhs.power ? id < rhs.id : power < rhs.power;
    }
};

class snake_list {
public:
    snake_list(const deque<snake>& raw) : a(raw) {
    }
    snake min() {
        snake ret = a.front();
        a.pop_front();
        return ret;
    }
    snake max() {
        deque<snake>* q;
        if (b.empty()) {
            q = &a;
        } else if (a.back() < b.back()) {
            q = &b;
        } else {
            q = &a;
        }
        snake ret = q->back();
        q->pop_back();
        return ret;
    }
    bool insert(snake s) {
        if (s < a.front()) {
            a.push_front(s);
            return true;
        } else {
            b.push_front(s);
            return false;
        }
    }
    int size() const {
        return a.size() + b.size();
    }
private:
    deque<snake> a, b;
};

bool choice[maxn];

bool dfs(snake_list& snakes, int depth) {
    if (snakes.size() == 1) {
        return choice[depth] = false;
    } else if (snakes.size() == 2) {
        return choice[depth] = true;
    } else {
        snake a = snakes.min(), b = snakes.max();
        snake c = { b.id, b.power - a.power };
        bool p = snakes.insert(c);
        if (p) {
            return choice[depth] = !dfs(snakes, depth + 1);
        } else {
            dfs(snakes, depth + 1);
            return choice[depth] = true;
        }
    }
}

int solve(const deque<snake>& raw, int n) {
    memset(choice, 0, sizeof(choice));
    snake_list snakes = raw;
    dfs(snakes, 1);
    #if 0
        puts("");
        for (int i = 1; i < n; i++) {
            printf("choice of turn %d is %d\n", i, choice[i]);
        }
        fflush(stdout);
    #endif
    for (int i = 1; i < n; i++) {
        if (!choice[i]) {
            return n - i + 1;
        }
    }
    return 1;
}

int main() {
    int t, n; scanf("%d%d", &t, &n); --t;
    deque<snake> raw(n);
    for (int i = 0; i < n; i++) {
        u64 s; scanf("%llu", &s);
        raw[i] = { i, s };
    }
    printf("%d\n", solve(raw, n));
    while (t--) {
        int p; scanf("%d", &p);
        while (p--) {
            int x; u64 s; scanf("%d%llu", &x, &s);
            raw[x - 1] = { x - 1, s };
        }
        printf("%d\n", solve(raw, n));
    }
}