把标记集合按极大连续段拆开,得分即若干不相交区间的收益之和;前缀/后缀斜率优化 DP 加 CDQ 分治凸包预处理出「强制标记 P」的最优值,每次询问 O(1)。
OJ: roj
题目 ID: 1794
难度:提高+/省选-
标签:动态规划斜率优化CDQ分治凸包python
创建: 2026-10-08 03:47
更新: 2026-10-08 03:47
形式化题目
给定长度为
有
于是整个问题等价于:选若干个互不相交的区间
正解
思路
朴素做法的瓶颈。 单次静态序列可以用 DP 求解:设
其中
关键观察:一次单点修改到底改变了什么? 看位置
未被标记:它只起断点作用,值是多少( 还是 )完全不影响得分。 此时最优值 = 前缀 的最优 + 后缀 的最优 = 。 被标记:它落在某个覆盖 的标记区间 中。把 改成 只让 这一个区间的元素和增加 ,于是总得分恰好减少 ,其余部分的决策不受影响。
所以若定义
动态询问就这样被压成了纯静态预处理——只要算出
求
内层就是对直线
求
把区间贡献展开并按
(
现在的任务变成:对每个
- 更新左半边
:条件 ,而只要 就自动有 。 于是对每个 只需在右半边 的凸包里查 , 得到 ;再对 做前缀最大值(把 内的所有 都取到), 一次性覆盖左半边所有 。 - 更新右半边
:对称地,对每个 在左半边 的凸包里查 ,得 ,再做后缀最大值覆盖右半边所有 。
两边的凸包斜率与查询
代码
#!/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-08 03:26
# update_at: 2026-10-08 03:47
import sys
NEG = -(10 ** 30) # 不可达哨兵:绝对值远大于任何真实得分
type Line = tuple[int, int] # 凸包上的一条直线 (斜率 k, 截距 b)
type Hull = list[Line] # 上凸包,斜率严格递增,支持查询 max(k*x+b)
def hull_add(hull: Hull, k: int, b: int) -> None:
"""往凸包里插入直线 y = kx + b;调用者保证斜率 k 单调递增。"""
if hull and hull[-1][0] == k: # 同斜率只保留截距更大的一条(防御性)
if hull[-1][1] >= b:
return
hull.pop()
while len(hull) >= 2:
(k1, b1), (k2, b2) = hull[-2], hull[-1]
# 中间那条线的最优区间为空 <=> 交点 x(前,中) >= 交点 x(中,新),化为整数交叉相乘
mid_is_useless = (b1 - b2) * (k - k2) >= (b2 - b) * (k2 - k1)
if not mid_is_useless:
break
hull.pop()
hull.append((k, b))
def hull_peak(hull: Hull, x: int) -> int:
"""查询凸包在 x 处的最大值:取值沿下标单峰,二分找峰。"""
lo, hi = 0, len(hull) - 1
while lo < hi:
mid = (lo + hi) >> 1
if hull[mid][0] * x + hull[mid][1] <= hull[mid + 1][0] * x + hull[mid + 1][1]:
lo = mid + 1
else:
hi = mid
return hull[lo][0] * x + hull[lo][1]
def build_dp_l(pre: list[int], n: int) -> list[int]:
"""dp_l[i]:只在原序列前缀 1..i 上标记的最大得分(dp_l[0] = 0)。
转移 = 要么不标记 i,要么拿 [m+1, i] 当最后一段(m = 0 表示从 1 开始,长度为 i-m)。
把长度平方项展开后,对 m 的部分是直线 y = m*x + c_m 在 x = -i 处取最大值。
"""
dp_l = [0] * (n + 1)
hull: Hull = []
for i in range(1, n + 1):
m = i - 1
before = dp_l[m - 1] if m else 0 # m = 0 时左边是空前缀
hull_add(hull, m, before + pre[m] + m * (m - 1) // 2)
cand = i * (i + 1) // 2 - pre[i] + hull_peak(hull, -i)
dp_l[i] = max(dp_l[i - 1], cand)
return dp_l
def build_dp_r(pre: list[int], n: int) -> list[int]:
"""dp_r[i]:只在原序列后缀 i..n 上标记的最大得分(dp_r[n+1] = dp_r[n+2] = 0)。
与 dp_l 完全对称,区间写成 [i, j-1],直线斜率改成 -j、查询点改成 x = i。
"""
dp_r = [0] * (n + 3)
hull: Hull = []
for i in range(n, 0, -1):
j = i + 1
hull_add(hull, -j, dp_r[j + 1] - pre[j - 1] + j * (j + 1) // 2)
cand = pre[i - 1] + i * (i - 1) // 2 + hull_peak(hull, i)
dp_r[i] = max(dp_r[i + 1], cand)
return dp_r
def cdq(left: list[int], right: list[int], n: int) -> list[int]:
"""CDQ 分治:mark_best[P] = max{left[a] + right[b] - a*b : a <= P <= b}。
按 P 落在下标的哪一半,把 "a <= P" 与 "b >= P" 两个条件各自消掉一个:
P 在左半时 b 自动 >= P,于是只需在右半 b 的凸包里对每个 a 查一次,再对 a 取前缀最大值;
P 在右半时完全对称,在左半 a 的凸包里对每个 b 查一次,再对 b 取后缀最大值。
"""
best = [NEG] * (n + 2)
stack = [(1, n)] # 显式栈,规避深递归与递归上限
while stack:
lo, hi = stack.pop()
if lo == hi:
best[lo] = max(best[lo], left[lo] + right[lo] - lo * lo)
continue
mid = (lo + hi) >> 1 # 左半 [lo,mid],右半 [mid+1,hi]
stack.append((lo, mid))
stack.append((mid + 1, hi))
hull: Hull = []
for b in range(hi, mid, -1): # b 递减使斜率 -b 递增,满足凸包插入顺序
hull_add(hull, -b, right[b])
ptr, size = 0, len(hull)
run = NEG
for a in range(lo, mid + 1): # 查询点 x = a 递增,最优下标单调右移
k, v = hull[ptr]
here = k * a + v
while ptr + 1 < size:
nk, nv = hull[ptr + 1]
step = nk * a + nv
if step < here:
break
ptr += 1
here = step
run = max(run, left[a] + here)
best[a] = max(best[a], run) # 前缀最大值覆盖所有 a <= P
hull = []
for a in range(mid, lo - 1, -1): # a 递减使斜率 -a 递增
hull_add(hull, -a, left[a])
ptr, suf = len(hull) - 1, NEG
for b in range(hi, mid, -1): # 查询点 x = b 递减,最优下标单调左移
k, v = hull[ptr]
here = k * b + v
while ptr > 0:
nk, nv = hull[ptr - 1]
step = nk * b + nv
if step < here:
break
ptr -= 1
here = step
suf = max(suf, right[b] + here)
best[b] = max(best[b], suf) # 后缀最大值覆盖所有 b >= P
return best
def build_mark_best(dp_l: list[int], dp_r: list[int], pre: list[int], n: int) -> list[int]:
"""mark_best[P]:原序列中强制标记位置 P 时的最大得分。
覆盖 P 的区间 [a,b] 贡献 dp_l[a-2] + f(a,b) + dp_r[b+2] = left[a] + right[b] - a*b,
于是 mark_best[P] = max{left[a] + right[b] - a*b : a <= P <= b},交给 cdq 求解。
"""
left = [0] * (n + 1) # 区间左端 a 的贡献,含 dp_l[a-2]
right = [0] * (n + 1) # 区间右端 b 的贡献,含 dp_r[b+2]
for a in range(1, n + 1):
left[a] = (dp_l[a - 2] if a >= 2 else 0) + pre[a - 1] + (a * a - 3 * a) // 2
for b in range(1, n + 1):
right[b] = dp_r[b + 2] - pre[b] + (b * b + 3 * b + 2) // 2
return cdq(left, right, n)
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
t = [0] + [next(data) for _ in range(n)]
pre = [0] * (n + 1)
for i in range(1, n + 1):
pre[i] = pre[i - 1] + t[i]
dp_l = build_dp_l(pre, n)
dp_r = build_dp_r(pre, n)
mark_best = build_mark_best(dp_l, dp_r, pre, n)
m = next(data)
out = []
for _ in range(m):
p, x = next(data), next(data)
# 不被覆盖时 T[p] 的值无关紧要;被覆盖时整段和多出 x - t[p],得分等量减少
uncovered = dp_l[p - 1] + dp_r[p + 1]
covered = mark_best[p] - x + t[p]
out.append(max(0, uncovered, covered))
sys.stdout.write('\n'.join(map(str, out)) + '\n')
if __name__ == "__main__":
solve()/**
* 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-08 03:26
* update_at: 2026-10-08 03:47
*/
// 1794《分数》
// 标记集合按极大连续段分解,长度 c 的一段贡献 c(c+1)/2 - 段内数字和。
// 于是 dpL / dpR 是两条斜率优化 DP;"强制标记 P"的最优值 markBest[P] 用 CDQ 分治 + 凸包求。
// 每组询问 (P,X) 的答案 = max(dpL[P-1] + dpR[P+1], markBest[P] - X + T[P])。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 300005;
const ll NEG = LLONG_MIN / 4; // 不可达哨兵:绝对值足够大,参与加减也不会溢出
int n, m;
ll T[MAXN]; // 原序列 T[1..n]
ll pre[MAXN]; // pre[i] = T[1] + ... + T[i]
ll dpL[MAXN]; // dpL[i]:只考虑前缀 1..i 时的最大得分(dpL[0] = 0)
ll dpR[MAXN]; // dpR[i]:只考虑后缀 i..n 时的最大得分(dpR[n+1] = 0)
ll leftPart[MAXN]; // 覆盖 P 的区间 [a,b] 中左端 a 的贡献
ll rightPart[MAXN]; // 覆盖 P 的区间 [a,b] 中右端 b 的贡献
ll markBest[MAXN]; // markBest[P]:原序列中强制标记位置 P 时的最大得分
ll cdqTmp[MAXN]; // CDQ 分治右半边的中间值,避免在递归函数里开大数组
// 直线 y = k*x + b
struct Line {
ll k, b;
};
// 上凸包:查询 max(k*x+b),插入的斜率必须严格递增
struct Hull {
Line ln[MAXN];
int sz;
void clear() { sz = 0; }
// 插入直线 y = kx + b;同斜率只保留截距更大的一条
void add(ll k, ll b) {
if (sz > 0 && ln[sz - 1].k == k) {
if (ln[sz - 1].b >= b) return;
--sz;
}
while (sz >= 2) {
Line p = ln[sz - 2]; // 斜率最小的一条
Line o = ln[sz - 1]; // 可能变冗余的中间线
Line q; // 新插入的线,斜率最大
q.k = k;
q.b = b;
// 中间线 o 的最优区间为空 <=> 交点 x(p,o) >= 交点 x(o,q)
__int128 lhs = (__int128)(p.b - o.b) * (q.k - o.k);
__int128 rhs = (__int128)(o.b - q.b) * (o.k - p.k);
if (lhs >= rhs) --sz;
else break;
}
ln[sz].k = k;
ln[sz].b = b;
++sz;
}
ll val(int i, ll x) const { return ln[i].k * x + ln[i].b; }
// 任意 x 的二分查询:凸包上取值随下标单峰
ll query(ll x) const {
int lo = 0, hi = sz - 1;
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (val(mid, x) <= val(mid + 1, x)) lo = mid + 1;
else hi = mid;
}
return val(lo, x);
}
} hull;
// 自然数快读:输入只含非负整数,跳过非数字字符即可
ll readInt() {
int ch = getchar();
while (ch != EOF && (ch < '0' || ch > '9')) ch = getchar();
ll v = 0;
while (ch >= '0' && ch <= '9') {
v = v * 10 + (ch - '0');
ch = getchar();
}
return v;
}
// 前缀 DP:dpL[i] = max(dpL[i-1], max_{m<i} { dpL[m-1] + C(i-m) - (pre[i]-pre[m]) })
// 其中 C(len) = len(len+1)/2,m 表示区间左端的前一个位置(m=0 表示从 1 开始)
void buildDpL() {
hull.clear();
for (int i = 1; i <= n; ++i) {
ll m = i - 1;
ll prevBest = (m == 0 ? 0 : dpL[m - 1]); // m = 0 时左边是空前缀
ll c = prevBest + pre[m] + m * (m - 1) / 2;
hull.add(m, c); // 直线 y = m*x + c
ll cand = (ll)i * (i + 1) / 2 - pre[i] + hull.query(-(ll)i);
dpL[i] = max(dpL[i - 1], cand);
}
}
// 后缀 DP(对称):dpR[i] = max(dpR[i+1], max_{j>i} { dpR[j+1] + C(j-i) - (pre[j-1]-pre[i-1]) })
// j 表示区间右端的后一个位置(j = n+1 表示到 n 结束)
void buildDpR() {
hull.clear();
dpR[n + 1] = 0;
dpR[n + 2] = 0;
for (int i = n; i >= 1; --i) {
ll j = i + 1;
ll e = dpR[j + 1] - pre[j - 1] + j * (j + 1) / 2;
hull.add(-j, e); // 直线 y = -j*x + e,查询 x = i
ll cand = pre[i - 1] + (ll)i * (i - 1) / 2 + hull.query(i);
dpR[i] = max(dpR[i + 1], cand);
}
}
// CDQ 分治:markBest[P] = max{ leftPart[a] + rightPart[b] - a*b : a <= P <= b }
void cdq(int lo, int hi) {
if (lo > hi) return;
if (lo == hi) {
// 只跨自己的区间 [lo, lo]
ll v = leftPart[lo] + rightPart[lo] - (ll)lo * lo;
markBest[lo] = max(markBest[lo], v);
return;
}
int mid = (lo + hi) >> 1;
// 情形一:P ∈ [lo, mid]。a <= P 需要保证,而 b >= mid+1 自动满足 b >= P。
// 先对每个 a 查出右半边最优的 b,再对 a 取前缀最大值,一次覆盖左半边所有 P。
hull.clear();
for (int b = hi; b >= mid + 1; --b) hull.add(-(ll)b, rightPart[b]); // 斜率 -b 递增
{
int ptr = 0;
ll best = NEG;
for (int a = lo; a <= mid; ++a) { // 查询 x = a 递增,最优下标单调右移
while (ptr + 1 < hull.sz && hull.val(ptr + 1, a) >= hull.val(ptr, a)) ++ptr;
ll v = leftPart[a] + hull.val(ptr, a);
if (v > best) best = v;
if (best > markBest[a]) markBest[a] = best;
}
}
// 情形二:P ∈ [mid+1, hi]。b >= P 需要保证,而 a <= mid 自动满足 a <= P。
hull.clear();
for (int a = mid; a >= lo; --a) hull.add(-(ll)a, leftPart[a]); // 斜率 -a 递增
{
int ptr = 0;
for (int b = mid + 1; b <= hi; ++b) { // 查询 x = b 递增
while (ptr + 1 < hull.sz && hull.val(ptr + 1, b) >= hull.val(ptr, b)) ++ptr;
cdqTmp[b] = rightPart[b] + hull.val(ptr, b);
}
ll suf = NEG;
for (int b = hi; b >= mid + 1; --b) { // P 可取 [P, hi] 内任意 b
if (cdqTmp[b] > suf) suf = cdqTmp[b];
if (suf > markBest[b]) markBest[b] = suf;
}
}
cdq(lo, mid);
cdq(mid + 1, hi);
}
int main() {
n = (int)readInt();
for (int i = 1; i <= n; ++i) {
T[i] = readInt();
pre[i] = pre[i - 1] + T[i];
}
buildDpL();
buildDpR();
// dpL[A-2] + f(A,B) + dpR[B+2] = leftPart[A] + rightPart[B] - A*B
for (int a = 1; a <= n; ++a) {
ll dl = (a >= 2 ? dpL[a - 2] : 0); // a <= 2 时区间左边是空前缀
leftPart[a] = dl + pre[a - 1] + ((ll)a * a - 3LL * a) / 2;
}
for (int b = 1; b <= n; ++b) {
rightPart[b] = dpR[b + 2] - pre[b] + ((ll)b * b + 3LL * b + 2) / 2;
}
for (int p = 1; p <= n; ++p) markBest[p] = NEG;
cdq(1, n);
m = (int)readInt();
string out;
out.reserve((size_t)m * 15);
for (int i = 0; i < m; ++i) {
ll p = readInt();
ll x = readInt();
ll noCover = dpL[p - 1] + dpR[p + 1]; // P 不标记:值改成什么都无所谓
ll withCover = markBest[p] - x + T[p]; // P 标记:整段和多了 x - T[p],收益等量减少
ll ans = max(noCover, withCover);
if (ans < 0) ans = 0; // 全部不标记也能得 0 分
out += to_string(ans);
out += '\n';
}
fwrite(out.data(), 1, out.size(), stdout);
return 0;
}复杂度
时间
总结
本题的核心是把「单点修改 + 询问最优值」的在线问题转成离线预处理:只要观察到修改值
与前缀 DP 相比,
实现上要注意两点:__int128 比较;答案不可为负,
所有不标记就是 0 分。
素材说明:本题素材源带自造数据生成脚本(
data.py),题面按一本通《高手训练篇》 原题文字重建,测试点为分层自造,与官方原始测试数据不保证一致。
图示解析
询问的两种处境
flowchart TD
Q["询问 (P, X):把 T_P 改成 X"] --> A["P 未被标记"]
Q --> B["P 被标记,落在覆盖 P 的区间 [a,b] 内"]
A --> A1["得分 = f[P-1] + g[P+1]<br/>与 X 无关"]
B --> B1["区间元素和增加 X - T_P<br/>得分 = B[P] - (X - T_P)"]
A1 --> R["答案取两者较大值"]
B1 --> R
CDQ 分治的一层
flowchart LR
subgraph SEG["区间 [lo, hi],中点 mid"]
L["a, P 在下标区间 lo..mid"] --- M["mid"] --- R2["b, P 在下标区间 mid+1..hi"]
end
L --> L1["P 不超过 mid:b 取右半边凸包最优<br/>再对 a 求前缀最大值"]
R2 --> R1["P 大于 mid:a 取左半边凸包最优<br/>再对 b 求后缀最大值"]