把一段连续操作抽象成需求函数 F(x)=max(need,x+cap),线段树合并三个字段,单点修改后根的保留和即答案。
OJ: roj
题目 ID: 1754
难度:提高+/省选-
标签:线段树栈python
创建: 2026-10-07 21:35
更新: 2026-10-07 21:35
形式化题目
有一个空栈和
:把 压入栈顶; :从栈顶弹出 个数,若栈中元素不足 个则全弹空(不会报错)。
随后有
记
正解
思路
暴力怎么看。 每次修改后重新模拟一遍:用一个数组当栈,压入就 push,弹出就 pop 若干次
(少于
换一个视角:把"保留哪些元素"改成一次配对。 先不管修改,只问"给定操作序列,谁留下来了"。
把一个压入操作看成供给 1 个元素,一个弹出操作看成需求
于是从左往右的模拟,等价于下面这次从右往左的贪心配对:每次弹出都把需求交给它左边最近的 可用供给,吃不完就继续往左找。这样配对完之后:
- 没有被吃掉的压入就是最终留在栈里的元素,答案 = 它们的值之和;
- 反过来从右往左扫,维护一个"还欠多少个元素"的计数器
(称为需求): 遇到弹出 就 ;遇到压入时,若 就吃掉它( ), 否则它存活并且 保持 。
把一段操作看成一个函数。 上面这个过程有一个很适合复用的结构:给一段连续操作
把
其中压入对应
关键观察:这个形状对复合封闭。 若左段
仍然是同一个形状,且
这说明 "两段操作的复合"是一个可结合的合并运算:线段树每个结点只存
再补一个
根的
其中
- 若
:没有需求,直接返回本段的 ; - 若
本段存活元素个数:本段被吃光,返回 ; - 否则需求落在某一侧,只需要往那一边走一层:
- 若
(右段能独自吸收), 左段收到的需求恒为 ,贡献固定 = , 于是累加这一项、把游标移到右儿子; - 否则右段被吃光,左段收到的需求变为
, 把游标移到左儿子。
- 若
其中"存活元素个数 =
于是得到完整做法。 用线段树维护序列,每个结点存
build:叶子按单个操作初始化,自底向上pull;- 每次修改:先把操作
的叶子改掉,再沿根到叶的路径自底向上重算 个结点,每个结点调用一次 的 ,单次修改 ; - 输出根的
(根对应"右侧无需求",正是题面要求的从空栈开始执行)。
正确性。 归纳地看:叶子上的 long long 无溢出风险。
一个手算例子。 取样例的第一次修改(2 0 3,把第 2 个操作改为“压入 3”),
此时操作序列是
| 位置 | 操作 | 进入的需求 |
结果 |
|---|---|---|---|
| 4 | 压入 3 | 0 | 存活,答案 |
| 3 | 弹出 2 | 0 | |
| 2 | 压入 3 | 2 | 被吃掉, |
| 1 | 压入 1 | 1 | 被吃掉, |
只有位置 4 的元素留下,和为
代码
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++ 版(同一算法):
/**
* 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代价,共 ;每次修改要重算路径上 个结点、每个结点一次 的 ,即单次 , 总计 。顶格时约 次基本运算, C++ 在 1 s 限制内很宽裕。 - 空间:线段树数组
个结点,每个结点三个 long long,。 - 与 C++ 解法的关系:两个版本是同一个算法的同一份实现思路,
合并式、
的下推分支、叶子定义逐行对应,复杂度同为 。 Python 版本的常数大得多(每个结点是元组、每次修改要重建 个元组), 的顶格数据下有 TLE 风险;这里不做算法降级, 需要保证时间时以 main.cpp为准。
总结
- 把"模拟"换成"配对":栈的弹出等价于"需求吃掉自己左边最近的可用供给", 于是"谁留下来"变成了一个从右往左的贪心配对问题,需求计数器不会变成负数, 这正是"弹不空就清空"在配对语言里的样子。
- 区间信息要选成对复合封闭的形状:
在复合下封闭,所以每段只要 两个数就能完整刻画它的行为; 选错形状(比如只存"最终栈大小")就无法从两个儿子推出父亲。 - 值域相关的字段不能简单相加:
的合并必须先把右段的缺口喂给左段, 这就是 里那个额外的 的来源; “存活元素个数 = ” 是让这次单链下推能安全停止的判据。 - 本题数据为自造:仓库里的测试数据由生成脚本按题面分层构造(边界、清空栈性质、 顶格随机、大和、恒空),并非官方原题数据;题意的理解与实现均以本题面的文字为准。
验证记录
- 样例:
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 组
(
、 、含弹空栈情形)以及 300 组中等规模 ( 、含 与 的清空极端), main.cpp全过;main.py与之再比对 470 组,结果一致。