半开区间 [l,r) 加 w,用差分数组:在 l 处 +w,在 r 处 −w,再从前到后前缀和还原每一段的负载,取最大值。
右端点 r 不加到第 r 段。n=105、m=105 时不能对每个任务暴力扫区间。
峰值可能很大,累加用 64 位。
常见假解:把 [l,r) 当成闭区间(在 r 也加);差分数组只在 r−1 减;用 32 位溢出。
骨干光纤被均分成 n 段,编号 0,1,…,n−1。运维下发若干切片任务 ops,每一项为 [l, r, load]:
load保证 0≤l<r≤n。若 ops 为空,所有段负载为 0。
请返回所有任务生效后,各段负载的最大值。
请实现:
maxLinkLoad(n: int, ops: int[][]) -> long
(峰值可能超过 32 位有符号整数,请使用 64 位整数。)
两行:
nops,形如 [[0, 2, 3], [1, 4, 2]]约束:
一个整数:峰值负载。
输入:
5
[[0, 2, 3], [1, 4, 2]]
输出:
5
说明:区间 [0,2) 加 3、[1,4) 加 2。各段负载为 3,5,2,2,0,峰值 5。右端点 r 对应的第 r 段不加本次负载。
输入:
3
[]
输出:
0
说明:没有任何切片,峰值 0。
输入:
1
[[0, 1, 9]]
输出:
9
说明:唯一一段 [0,1) 加 9。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.