栈的维护

GitHub跳转原题关系图返回列表

把一段连续操作抽象成需求函数 F(x)=max(need,x+cap),线段树合并三个字段,单点修改后根的保留和即答案。

OJ: roj

题目 ID: 1754

难度:提高+/省选-

标签:线段树栈python

创建: 2026-10-07 21:35

更新: 2026-10-07 21:35

形式化题目

有一个空栈和 mm 个依次执行的操作,第 ii 个操作为 (ki,vi)(k_i, v_i):

  • ki=0k_i = 0:把 viv_i 压入栈顶;
  • ki=1k_i = 1:从栈顶弹出 viv_i 个数,若栈中元素不足 viv_i 个则全弹空(不会报错)。

随后有 qq 次修改,第 tt 次修改给出 (c,k,v)(c, k, v),表示把第 cc 个操作的两个参数同时改成 (k,v)(k, v)(即 kc←k, vc←vk_c \leftarrow k,\ v_c \leftarrow v,改动会保留到后续修改)。 每次修改后,求从空栈开始依次执行当前全部 mm 个操作之后,栈中剩余元素之和。

记 S⊆{1,…,m}S \subseteq \{1, \dots, m\} 为"执行完所有操作后仍然留在栈中"的压入操作集合, 则答案为 ∑i∈Svi\sum_{i \in S} v_i。题目要求对每次修改都重新求这个和, m,q⩽2×105m, q \leqslant 2 \times 10^5,1⩽vi⩽1041 \leqslant v_i \leqslant 10^4。 由于每个元素值不超过 10410^4、最多 2×1052 \times 10^5 个元素,答案不超过 2×1092 \times 10^9。

正解

思路

暴力怎么看。 每次修改后重新模拟一遍:用一个数组当栈,压入就 push,弹出就 pop 若干次 (少于 vv 个时清空)。单次模拟 O(m+∑v)O(m + \sum v),总共 O(qm)O(qm),在 m=q=2×105m = q = 2 \times 10^5 时 是 4×10104 \times 10^{10} 次操作,完全不可行。瓶颈很明确:每次只改一个操作,却要把整条操作序列 重算一遍。

换一个视角:把"保留哪些元素"改成一次配对。 先不管修改,只问"给定操作序列,谁留下来了"。 把一个压入操作看成供给 1 个元素,一个弹出操作看成需求 vv 个元素。栈的后进先出意味着: 被弹出的元素永远是当前最靠右(最靠近它)的未被吃掉的压入。

于是从左往右的模拟,等价于下面这次从右往左的贪心配对:每次弹出都把需求交给它左边最近的 可用供给,吃不完就继续往左找。这样配对完之后:

  • 没有被吃掉的压入就是最终留在栈里的元素,答案 = 它们的值之和;
  • 反过来从右往左扫,维护一个"还欠多少个元素"的计数器 yy(称为需求): 遇到弹出 vv 就 y+=vy \mathrel{+}= v;遇到压入时,若 y>0y > 0 就吃掉它(y−=1y \mathrel{-}= 1), 否则它存活并且 yy 保持 00。

yy 永远不会变成负数——这正是"弹不空就清空"这条规则在配对语言里的样子:需求吃不到供给时 就直接消失,绝不会反向产生供给。

把一段操作看成一个函数。 上面这个过程有一个很适合复用的结构:给一段连续操作 [l,r][l, r] 从右端灌进去 xx 个需求,那么从这段的左端出去的需求个数是确定的,记作 F[l,r](x)F_{[l,r]}(x)。对单个操作:

F(x)={max⁡(0,  x−1),压入x+v,弹出 vF(x) = \begin{cases} \max(0,\; x - 1), & \text{压入} \\ x + v, & \text{弹出 } v \end{cases}

把 x⩾0x \geqslant 0 代进去可以发现,两类函数都能写成同一个形状

F(x)=max⁡(need,  x+cap),F(x) = \max\bigl(\texttt{need},\; x + \texttt{cap}\bigr),

其中压入对应 (cap,need)=(−1,0)(\texttt{cap}, \texttt{need}) = (-1, 0),弹出 vv 对应 (v,v)(v, v)。

关键观察:这个形状对复合封闭。 若左段 LL、右段 RR 都形如上式,那么

FLR(x)=FL(FR(x))=FL(max⁡(needR, x+capR))=max⁡(needL, needR+capL, x+capR+capL), F_{LR}(x) = F_L\bigl(F_R(x)\bigr) = F_L\bigl(\max(\texttt{need}_R,\ x + \texttt{cap}_R)\bigr) = \max\bigl(\texttt{need}_L,\ \texttt{need}_R + \texttt{cap}_L,\ x + \texttt{cap}_R + \texttt{cap}_L\bigr),

仍然是同一个形状,且

capLR=capL+capR,needLR=max⁡(needL, needR+capL).\texttt{cap}_{LR} = \texttt{cap}_L + \texttt{cap}_R, \qquad \texttt{need}_{LR} = \max\bigl(\texttt{need}_L,\ \texttt{need}_R + \texttt{cap}_L\bigr).

这说明 "两段操作的复合"是一个可结合的合并运算:线段树每个结点只存 (cap,need)(\texttt{cap}, \texttt{need}), 自底向上就能把整段操作合成一个函数,而整段在 x=0x = 0 时的行为(也就是我们要的答案所在) 只依赖根结点。

cap\texttt{cap} 的含义也清楚了:cap=∑(ki=1)vi−#{ki=0}\texttt{cap} = \sum_{(k_i=1)} v_i - \#\{k_i = 0\}, 即"本段弹出的总数减去压入的次数";它就是"需求灌进去之后,出去的需求比进来多多少"。

再补一个 sum\texttt{sum} 字段,才能回答"和是多少"。 只知道需求个数还不够,我们要的是 保留元素的值之和。于是给每个结点再加一个字段

sum=从右侧灌入 0 个需求时,本段最终保留的元素值之和。\texttt{sum} = \text{从右侧灌入 0 个需求时,本段最终保留的元素值之和。}

根的 sum\texttt{sum} 就是答案。问题是 sum\texttt{sum} 不能由两个儿子的 sum\texttt{sum} 直接相加: 右段在无需求时向外吐出的需求 needR\texttt{need}_R 会继续吃掉左段靠右的存活元素。 正确的合并式是

sumLR=sumR+G(L, needR),\texttt{sum}_{LR} = \texttt{sum}_R + G\bigl(L,\ \texttt{need}_R\bigr),

其中 G(k,y)G(k, y) 表示"结点 kk 从右侧收到 yy 个需求时保留的元素之和"。 右段自己收到的是 00,所以它完整保留 sumR\texttt{sum}_R;左段必须先应付右段传来的 needR\texttt{need}_R。

GG 能在一条链上 O(log⁡m)O(\log m) 算完。 需求只吃掉最靠右的存活元素,所以从根往下看, 只需要决定"这批需求是否被右半段吃光":

  • 若 y⩽0y \leqslant 0:没有需求,直接返回本段的 sum\texttt{sum};
  • 若 y⩾y \geqslant 本段存活元素个数:本段被吃光,返回 00;
  • 否则需求落在某一侧,只需要往那一边走一层:
    • 若 y⩽needR−capRy \leqslant \texttt{need}_R - \texttt{cap}_R(右段能独自吸收), 左段收到的需求恒为 needR\texttt{need}_R,贡献固定 = sumk−sumR\texttt{sum}_k - \texttt{sum}_R, 于是累加这一项、把游标移到右儿子;
    • 否则右段被吃光,左段收到的需求变为 FR(y)=y+capRF_R(y) = y + \texttt{cap}_R, 把游标移到左儿子。

其中"存活元素个数 = need−cap\texttt{need} - \texttt{cap}"这条等式由配对语义直接给出: cap=供给数−需求数\texttt{cap} = \text{供给数} - \text{需求数}、need=没被满足的需求数\texttt{need} = \text{没被满足的需求数}, 两者相加正好是没被吃掉的供给数(叶子上一验证即成立,复合式也保持它)。 每层只走一个儿子,所以 GG 的代价是 O(log⁡m)O(\log m)。

于是得到完整做法。 用线段树维护序列,每个结点存 (cap,need,sum)(\texttt{cap}, \texttt{need}, \texttt{sum}):

  1. build:叶子按单个操作初始化,自底向上 pull;
  2. 每次修改:先把操作 cc 的叶子改掉,再沿根到叶的路径自底向上重算 O(log⁡m)O(\log m) 个结点,每个结点调用一次 O(log⁡m)O(\log m) 的 GG,单次修改 O(log⁡2m)O(\log^2 m);
  3. 输出根的 sum\texttt{sum}(根对应"右侧无需求",正是题面要求的从空栈开始执行)。

正确性。 归纳地看:叶子上的 FF 与"压入/弹出一次"的真实行为一致; 复合公式由 FLR=FL∘FRF_{LR} = F_L \circ F_R 逐步代入得到,与真实串行执行一致(函数复合就是"先右后左"), 故每个结点存的 (cap,need)(\texttt{cap}, \texttt{need}) 都正确刻画该段的行为。 sum\texttt{sum} 的合并式把右段的缺口 needR\texttt{need}_R 如实喂给左段, 而"需求只吃最靠右的存活元素"保证了 GG 的单链下推不会遗漏任何被吃掉的元素; 根结点收到 00 个需求,与"从空栈开始执行全部操作"完全对应,故根 sum\texttt{sum} 即答案。 所有运算只用加法和 max⁡\max,其中 cap\texttt{cap} 的下界不比 −m-m 更深、 need\texttt{need}、sum\texttt{sum} 不超过 2×1092 \times 10^9,用 long long 无溢出风险。

一个手算例子。 取样例的第一次修改(2 0 3,把第 2 个操作改为“压入 3”), 此时操作序列是 (压1, 压3, 弹2, 压3)(\text{压}1,\ \text{压}3,\ \text{弹}2,\ \text{压}3)。 从右往左走一遍配对过程:

位置 操作 进入的需求 yy 结果
4 压入 3 0 存活,答案 +3+3,yy 仍为 0
3 弹出 2 0 y←2y \leftarrow 2
2 压入 3 2 被吃掉,y←1y \leftarrow 1
1 压入 1 1 被吃掉,y←0y \leftarrow 0

只有位置 4 的元素留下,和为 33,与样例第一行输出一致; 直接模拟也能验证:压入 1、压入 3 之后栈是 [1,3][1, 3],弹出 2 个把两个元素都拿走, 再压入 3,最终剩 [3][3]。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 21:30
# update_at: 2026-10-07 21:35

import sys

# 每个线段树结点用一个三元组 (cap, need, kept) 描述一段连续操作,含义固定如下:
#   cap  —— 该段“弹出值之和 - 压入次数”,即需求函数 F(x) = max(need, x + cap) 的斜率
#   need —— 右侧没有外部需求时,该段仍需继续向左侧弹出的个数,即 F(0)
#   kept —— 右侧没有外部需求时,该段最终留在栈中的元素之和
# 其中 x 是从这段右侧灌进来的弹出需求个数。因为 F 恒是这个形状,两段复合后形状不变
# (cap 相加、need 取 max),所以结点信息可以自底向上合并;need - cap 恰好是
# “无外部需求时存活的元素个数”,用来判断一个需求会不会把整段吃光。
type Node = tuple[int, int, int]  # (cap, need, kept)
type Seg = list[Node]             # 满二叉线段树,下标 1 为根,空位用恒等段填充

IDLE: Node = (0, 0, 0)  # 恒等段 F(x) = x:既不供给也不索取,用于右端对齐的补位


def leaf_of(kind: int, value: int) -> Node:
    """一个操作对应的叶子:压入 v 供给 1 个元素,弹出 v 是纯需求 v。"""
    return (value, value, 0) if kind else (-1, 0, value)


def keep_sum(seg: Seg, k: int, demand: int) -> int:
    """结点 k 在右侧灌进 demand 个需求时,最终留在栈中的元素之和。

    需求总是先吃掉最靠右的压入,所以只需沿一条从根到叶的链下推:
    右儿子能吸收需求就整段保留左儿子,吸收不完就把剩余需求转交左儿子。
    """
    total = 0
    while True:
        cap, need, kept = seg[k]
        if demand <= 0:
            return total + kept      # 本段没有需求,整段原样保留
        alive = need - cap           # 本段存活元素个数,也是能吸收的需求上限
        if demand >= alive:
            return total             # 需求吃光本段全部存活元素
        ls = k * 2
        rs = ls + 1
        cap_r, need_r, kept_r = seg[rs]
        room_r = need_r - cap_r  # 右儿子能独自吸收的需求上限
        if demand <= room_r:
            # 右儿子独自吸收需求:左儿子收到的需求恒为 need_r,贡献固定不变
            total += kept - kept_r
            k = rs
        else:
            # 右儿子被吃光,剩下的需求 y 满足 y > need_r,此时 F_r(y) = y + cap_r
            demand += cap_r
            k = ls


def refresh(seg: Seg, k: int) -> None:
    """用左右儿子重算结点 k:先让右儿子消化外部需求,再把它的缺口转交左儿子。"""
    ls = k * 2
    rs = ls + 1
    cap_l, need_l, _ = seg[ls]
    cap_r, need_r, kept_r = seg[rs]
    seg[k] = (cap_l + cap_r,
              max(need_l, need_r + cap_l),
              kept_r + keep_sum(seg, ls, need_r))


def build(ops: list[Node]) -> tuple[Seg, int]:
    """把 m 个操作装进满二叉线段树,返回 (树, 叶子偏移 base)。

    叶子数取不小于 m 的 2 的幂,右端空位是恒等段,因此第 c 个操作落在 base + c - 1。
    """
    base = 1
    while base < len(ops):
        base <<= 1
    seg: Seg = [IDLE] * (2 * base)
    for i, node in enumerate(ops):
        seg[base + i] = node
    for k in range(base - 1, 0, -1):
        refresh(seg, k)
    return seg, base


def update(seg: Seg, base: int, index: int, node: Node) -> None:
    """把第 index 个操作改成 node,并自底向上重算受影响的那条根到叶路径。"""
    pos = base + index - 1
    seg[pos] = node
    pos >>= 1
    while pos:               # 只有一条链上的结点变了
        refresh(seg, pos)
        pos >>= 1


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    m, q = next(data), next(data)

    ops: list[Node] = []  # 第 c 个操作(1 起编号)的叶子信息,修改时原地覆盖
    for _ in range(m):
        ops.append(leaf_of(next(data), next(data)))
    seg, base = build(ops)

    out: list[str] = []
    for _ in range(q):
        index = next(data)       # 题面的 c
        ops[index - 1] = leaf_of(next(data), next(data))
        update(seg, base, index, ops[index - 1])
        out.append(str(seg[1][2]))  # 根在“右侧无需求”下保留的和就是答案

    sys.stdout.write('\n'.join(out) + '\n')


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 21:30
 * update_at: 2026-10-07 21:35
 */
// 一本通 1754《栈的维护》
//
// 把一段连续操作看成一个函数 F(x) = max(need, x + cap):
//   x 是从这段右侧灌进来的"弹出需求"个数,F(x) 是最终还要继续向左侧弹出的个数。
// 单个叶子:压入 v -> F(x) = max(0, x - 1);弹出 v -> F(x) = x + v。
// 两个函数复合仍是这个形状:F_{L+R}(x) = F_L(F_R(x)) = max(max(needL, needR + capL), x + capL + capR)。
// 因此每个结点存 cap(= 弹出值之和 - 压入次数)、need(= F(0))就够了。
// 再加上 sum = "右侧没有需求时本段留在栈中的元素之和",根结点的 sum 就是答案。
// 需求会从右往左吃掉压入的元素,所以 sum 不能由儿子的 sum 直接相加,
// 需要一次 O(log m) 的单链下推(retain);单点修改要重算 O(log m) 个结点,总复杂度 O(log^2 m)。
// 元素和的上界约 2e5*1e4 = 2e9,cap/need/sum 全部用 long long。
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 200000 + 5;

struct Op {
    ll k;  // 0 压入,1 弹出
    ll v;  // k=0 时为入栈的数,k=1 时为弹出个数
};

struct Node {
    ll cap;  // 本段 cap 之和:弹出值之和减去压入次数,可以为负
    ll need; // 本段在右侧没有外部需求时仍需向左侧弹出的个数,恒 >= cap
    ll sum;  // 右侧没有外部需求时,本段最终留在栈中的元素之和
};

int m, q;
int base;      // 线段树叶子数,取 2 的幂,右端空位用恒等段(F(x) = x)填充
int leafOf;    // 第 1 个操作对应的叶子下标
Op op[MAXN];
Node seg[MAXN * 4];  // 2*base 最大 524288 < MAXN*4

// 本段在右侧灌进 y 个需求时,最终留在栈中的元素之和。
// 只能沿单条链下推:需求先吃掉右下方的压入,最多走 O(log m) 步。
ll retain(int k, ll y) {
    ll kept = 0;
    while (true) {
        if (y <= 0) return kept + seg[k].sum;             // 没有需求,整段保留
        if (y >= seg[k].need - seg[k].cap) return kept;   // 需求吃光本段全部存活元素
        int ls = k << 1, rs = ls | 1;
        ll roomR = seg[rs].need - seg[rs].cap;            // 右儿子能吸收的需求上限
        if (y <= roomR) {
            // 右儿子独自吸收:左儿子收到的需求恒为 needR,故左儿子贡献固定
            kept += seg[k].sum - seg[rs].sum;
            k = rs;
        } else {
            // 右儿子被吃光,剩下的需求 y + capR 灌进左儿子
            y += seg[rs].cap;
            k = ls;
        }
    }
}

// 用左右儿子重算 k。sum 不能直接相加:右儿子的 needR 会向左侧(即左儿子)要元素
void pull(int k) {
    int ls = k << 1, rs = ls | 1;
    seg[k].cap = seg[ls].cap + seg[rs].cap;
    seg[k].need = max(seg[ls].need, seg[rs].need + seg[ls].cap);
    seg[k].sum = seg[rs].sum + retain(ls, seg[rs].need);
}

// 叶子:压入 v 是"供给 1 个元素",弹出 v 是"纯需求 v"
void set_leaf(int k, ll kk, ll vv) {
    if (kk == 1) {
        seg[k].cap = vv;
        seg[k].need = vv;
        seg[k].sum = 0;
    } else {
        seg[k].cap = -1;
        seg[k].need = 0;
        seg[k].sum = vv;
    }
}

int main() {
    if (scanf("%d %d", &m, &q) != 2) return 0;
    base = 1;
    while (base < m) base <<= 1;
    leafOf = base;  // 第 1 个操作用下标 1,落在 base + 1 - 1 = base 这个叶子上
    for (int i = 1; i <= m; ++i) scanf("%lld %lld", &op[i].k, &op[i].v);
    for (int i = 1; i <= 2 * base; ++i) {  // 空位是恒等段,不影响结果
        seg[i].cap = 0;
        seg[i].need = 0;
        seg[i].sum = 0;
    }
    for (int i = 1; i <= m; ++i) set_leaf(leafOf + i - 1, op[i].k, op[i].v);
    for (int k = base - 1; k >= 1; --k) pull(k);
    for (int i = 1; i <= q; ++i) {
        int c;
        ll kk, vv;
        scanf("%d %lld %lld", &c, &kk, &vv);
        op[c].k = kk;
        op[c].v = vv;
        set_leaf(leafOf + c - 1, kk, vv);
        for (int k = (leafOf + c - 1) >> 1; k >= 1; k >>= 1) pull(k);
        printf("%lld\n", seg[1].sum);  // 根在"右侧无需求"下保留的和就是答案
    }
    return 0;
}

复杂度

  • 时间:建树每次 pull 代价 O(log⁡m)O(\log m),共 O(mlog⁡m)O(m\log m);每次修改要重算路径上 O(log⁡m)O(\log m) 个结点、每个结点一次 O(log⁡m)O(\log m) 的 GG,即单次 O(log⁡2m)O(\log^2 m), 总计 O((m+qlog⁡m)log⁡m)O\bigl((m + q\log m)\log m\bigr)。顶格时约 6×1076 \times 10^7 次基本运算, C++ 在 1 s 限制内很宽裕。
  • 空间:线段树数组 4m4m 个结点,每个结点三个 long long,O(m)O(m)。
  • 与 C++ 解法的关系:两个版本是同一个算法的同一份实现思路, 合并式、GG 的下推分支、叶子定义逐行对应,复杂度同为 O((m+qlog⁡m)log⁡m)O((m + q\log m)\log m)。 Python 版本的常数大得多(每个结点是元组、每次修改要重建 O(log⁡m)O(\log m) 个元组), q=2×105q = 2 \times 10^5 的顶格数据下有 TLE 风险;这里不做算法降级, 需要保证时间时以 main.cpp 为准。

总结

  • 把"模拟"换成"配对":栈的弹出等价于"需求吃掉自己左边最近的可用供给", 于是"谁留下来"变成了一个从右往左的贪心配对问题,需求计数器不会变成负数, 这正是"弹不空就清空"在配对语言里的样子。
  • 区间信息要选成对复合封闭的形状:F(x)=max⁡(need,x+cap)F(x) = \max(\texttt{need}, x + \texttt{cap}) 在复合下封闭,所以每段只要 (cap,need)(\texttt{cap}, \texttt{need}) 两个数就能完整刻画它的行为; 选错形状(比如只存"最终栈大小")就无法从两个儿子推出父亲。
  • 值域相关的字段不能简单相加:sum\texttt{sum} 的合并必须先把右段的缺口喂给左段, 这就是 O(log⁡2m)O(\log^2 m) 里那个额外的 log⁡\log 的来源; “存活元素个数 = need−cap\texttt{need} - \texttt{cap}” 是让这次单链下推能安全停止的判据。
  • 本题数据为自造:仓库里的测试数据由生成脚本按题面分层构造(边界、清空栈性质、 顶格随机、大和、恒空),并非官方原题数据;题意的理解与实现均以本题面的文字为准。

验证记录

  • 样例:4 3 / 0 1 / 0 2 / 1 2 / 0 3 加三次修改,期望 3 4 0; main.cpp 与 main.py 实跑输出均为 3 4 0。
  • 真实数据:data/ 的 10 个测试点,main.cpp 与 main.py 均与 .out 逐行一致。
  • 小规模随机对拍:与"每次修改后直接模拟栈"的暴力实现比对 500 组 (m⩽12m \leqslant 12、v∈{3,10,100}v \in \{3, 10, 100\}、含弹空栈情形)以及 300 组中等规模 (m⩽150m \leqslant 150、含 v=1v = 1 与 v⩾5000v \geqslant 5000 的清空极端),main.cpp 全过; main.py 与之再比对 470 组,结果一致。