This problem centers on dynamically maintaining and querying the minimum number of positive rating increments needed to offset a cumulative negative rating sum—effectively determining how many smallest available positive values must be selected (in sorted order) so their total is at least the absolute value of the negative sum.

The core insight is greedy: to minimize the count of positive elements used, always pick the smallest available positives first—this maximizes efficiency per unit count. Thus, after collecting all positive values, we sort and compress them (coordinate compression), then build a segment tree that supports two operations:

• Point updates: insert or remove a positive value (tracking both its contribution to the total sum and its count).
• Prefix-sum–aware queries: given a target T = -neg, find the smallest k such that the sum of the k smallest stored positives is ≥ T.

Two implementation strategy are viable:

1. Direct binary search on segment tree index: The segment tree stores per-leaf node the value and frequency; internal nodes aggregate sum and count. A custom rangeQuery function traverses the tree to simulate "fetching the first k smallest elements’ sum" in O(log N). Then, binary search over k ∈ [0, total_positive_count] yields the answer in O(log²N) per query.
2. Tree-assisted k-th threshold descent: Instead of outer binary search, the segment tree itself implements a "find minimal k where prefix-sum ≥ T" by descending left-to-right while comparing accumulated left subtree sum against T. This achieves O(log N) per query but requires careful handling of fractional contributions when leaf nodes contain duplicates (e.g., multiple occurrences of same value).

In both variants, negative values are tracked separately as a running sum (neg). Each update adjusts either the positive multiset (via coordinate-compressed index) or neg, ensuring consistency across queries.

Below is a refactored, idiomatic C++ implementation using straetgy #1—cleaner abstraction, renamed types, and simplified logic flow:

#include <bits/stdc++.h>

using i64 = long long;

struct Node {
    i64 total = 0;
    int count = 0;
};

Node operator+(const Node& a, const Node& b) {
    return {a.total + b.total, a.count + b.count};
}

template <typename T>
class SegTree {
private:
    int n;
    std::vector<T> tree;

    void pull(int idx) {
        tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
    }

    void build(int idx, int l, int r, const std::vector<T>& init) {
        if (r - l == 1) {
            tree[idx] = init[l];
            return;
        }
        int mid = (l + r) / 2;
        build(2 * idx, l, mid, init);
        build(2 * idx + 1, mid, r, init);
        pull(idx);
    }

    void update(int idx, int l, int r, int pos, const T& delta) {
        if (r - l == 1) {
            tree[idx] = tree[idx] + delta;
            return;
        }
        int mid = (l + r) / 2;
        if (pos < mid) update(2 * idx, l, mid, pos, delta);
        else update(2 * idx + 1, mid, r, pos, delta);
        pull(idx);
    }

    // Returns sum of smallest 'k' elements in range [ql, qr)
    i64 query_k_sum(int idx, int l, int r, int ql, int qr, int k) const {
        if (k <= 0 || l >= qr || r <= ql || k > tree[idx].count) return 0;
        if (r - l == 1) {
            i64 val_per_unit = tree[idx].total / tree[idx].count;
            return static_cast<i64>(val_per_unit) * k;
        }
        int mid = (l + r) / 2;
        i64 left_sum = tree[2 * idx].total;
        int left_cnt = tree[2 * idx].count;
        if (k <= left_cnt) {
            return query_k_sum(2 * idx, l, mid, ql, qr, k);
        }
        return left_sum + query_k_sum(2 * idx + 1, mid, r, ql, qr, k - left_cnt);
    }

public:
    SegTree(int size) : n(size), tree(4 * size) {}
    
    void build(const std::vector<T>& init) {
        build(1, 0, n, init);
    }
    
    void update(int pos, const T& delta) {
        update(1, 0, n, pos, delta);
    }
    
    i64 query_k_sum(int k) const {
        return query_k_sum(1, 0, n, 0, n, k);
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;

    std::vector<int> arr(n);
    i64 neg_sum = 0;
    std::vector<int> positives;

    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
        if (arr[i] > 0) positives.push_back(arr[i]);
        else neg_sum += arr[i];
    }

    std::vector<std::pair<int, int>> queries(q);
    for (auto& [idx, val] : queries) {
        std::cin >> idx >> val;
        --idx;
        if (val > 0) positives.push_back(val);
    }

    std::sort(positives.begin(), positives.end());
    positives.erase(std::unique(positives.begin(), positives.end()), positives.end());

    int m = positives.size();
    std::vector<Node> init(m + 1); // extra slot for safety
    SegTree<Node> seg(m + 1);
    seg.build(init);

    std::vector<int> pos_index(n, -1);
    for (int i = 0; i < n; ++i) {
        if (arr[i] > 0) {
            pos_index[i] = std::lower_bound(positives.begin(), positives.end(), arr[i]) - positives.begin();
            seg.update(pos_index[i], {static_cast<i64>(arr[i]), 1});
        }
    }

    for (const auto& [idx, val] : queries) {
        if (arr[idx] > 0) {
            seg.update(pos_index[idx], {-static_cast<i64>(arr[idx]), -1});
        } else {
            neg_sum -= arr[idx];
        }

        arr[idx] = val;

        if (val > 0) {
            pos_index[idx] = std::lower_bound(positives.begin(), positives.end(), val) - positives.begin();
            seg.update(pos_index[idx], {static_cast<i64>(val), 1});
        } else {
            neg_sum += val;
        }

        i64 target = -neg_sum;
        if (target <= 0) {
            std::cout << "1\n";
            continue;
        }

        int lo = 0, hi = m + 1;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (seg.query_k_sum(mid) >= target) {
                hi = mid - 1;
            } else {
                lo = mid;
            }
        }
        std::cout << lo + 1 << '\n';
    }

    return 0;
}