思路与算法

线段树把一段操作压缩成三项：仍需向左弹出的数量del、存活压入数c、存活值之和sum。合并A后B时，B的del消耗A的末尾压入，A保留max(0,A.c-B.del)个最早存活元素，B自身存活元素接在其后；不足部分叠加到del。借助树结构递归查询一个节点存活序列的前k项和，完成sum合并。

正确性说明

任何操作段对先前栈的影响都只有弹掉若干栈顶后接上该段未被自身后续弹出的压入序列。上述三项及子树中的存活前缀查询恰表示这个规范形式。合并按真实执行顺序消除B弹出与A压入，归纳可得根的存活和就是从空栈执行全部操作的答案。

复杂度

每次前缀和查询沿一条树路径O(logM)，点修改O(logM)层各合并一次，总O(log²M)。本实现初建逐个点修改，保守O(Mlog²M)；Q次修改O(Qlog²M)，空间O(M)、递归栈O(logM)。

易错点

弹出超出当前栈时多余量需要保留，以便与左侧操作合并，但最终空栈不会负长。前缀查询对象是内部消除后的存活序列，不能按原操作下标直接求和。总和用64位。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int c = 0, del = 0;
    long long sum = 0;
};
vector<Node> t;
long long prefix(int v, int k) {
    if (k <= 0)
        return 0;
    if (k >= t[v].c)
        return t[v].sum;
    int a = max(0, t[v * 2].c - t[v * 2 + 1].del);
    if (k <= a)
        return prefix(v * 2, k);
    return t[v].sum - t[v * 2 + 1].sum + prefix(v * 2 + 1, k - a);
}
void pull(int v) {
    auto a = t[v * 2], b = t[v * 2 + 1];
    int keep = max(0, a.c - b.del);
    t[v].c = keep + b.c;
    t[v].del = a.del + max(0, b.del - a.c);
    t[v].sum = prefix(v * 2, keep) + b.sum;
}
void setleaf(int v, int k, int x) {
    t[v] = Node();
    if (k)
        t[v].del = x;
    else {
        t[v].c = 1;
        t[v].sum = x;
    }
}
void change(int v, int l, int r, int p, int k, int x) {
    if (l == r) {
        setleaf(v, k, x);
        return;
    }
    int m = (l + r) / 2;
    if (p <= m)
        change(v * 2, l, m, p, k, x);
    else
        change(v * 2 + 1, m + 1, r, p, k, x);
    pull(v);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, q;
    cin >> m >> q;
    t.resize(4 * m);
    for (int i = 0; i < m; i++) {
        int k, v;
        cin >> k >> v;
        change(1, 0, m - 1, i, k, v);
    }
    while (q--) {
        int p, k, v;
        cin >> p >> k >> v;
        change(1, 0, m - 1, p - 1, k, v);
        cout << t[1].sum << '\n';
    }
}