分数

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

把标记集合按极大连续段拆开,得分即若干不相交区间的收益之和;前缀/后缀斜率优化 DP 加 CDQ 分治凸包预处理出「强制标记 P」的最优值,每次询问 O(1)。

OJ: roj

题目 ID: 1794

难度:提高+/省选-

标签:动态规划斜率优化CDQ分治凸包python

创建: 2026-10-08 03:47

更新: 2026-10-08 03:47

形式化题目

给定长度为 NN 的序列 T1,…,TNT_1, \dots, T_N。选择一个标记集合 S⊆{1,…,N}S \subseteq \{1, \dots, N\}, 它按极大连续段分解成若干互不相邻的区间。若某段区间为 [l,r][l, r],长度 c=r−l+1c = r - l + 1, 则它贡献 c(c+1)2\dfrac{c(c+1)}{2}(完全落在段内的子区间个数)减去 ∑i=lrTi\sum_{i=l}^{r} T_i (被标记数字之和)。总得分是所有极大连续段贡献之和。

有 MM 组询问,第 ii 组给出 Pi,XiP_i, X_i,要求把 TPiT_{P_i} 临时改成 XiX_i 后总得分的最大值。 每组询问相互独立。

于是整个问题等价于:选若干个互不相交的区间 [l,r][l, r],最大化 ∑(c(c+1)2−∑T)\sum \left( \dfrac{c(c+1)}{2} - \sum T \right),每组询问把某个 TPT_P 换成 XX 后重求这个最大值。

正解

思路

朴素做法的瓶颈。 单次静态序列可以用 DP 求解:设 f[i]f[i] 为前缀 1..i1..i 的最优得分, 枚举最后一个标记段 [m+1,i][m+1, i]:

f[i]=max⁡(f[i−1],  max⁡0≤m<i{f[m]+(i−m)(i−m+1)2−(Si−Sm)})f[i] = \max\left(f[i-1],\; \max_{0 \le m < i}\Big\{ f[m] + \tfrac{(i-m)(i-m+1)}{2} - (S_i - S_m) \Big\}\right)

其中 SS 为前缀和,m=0m = 0 表示 f[0]=0f[0]=0。内层是斜率优化,单次静态序列可 O(N)O(N) 或 O(Nlog⁡N)O(N \log N) 解决。但 MM 组询问若各跑一次就是 O(NM)=9×1010O(NM) = 9 \times 10^{10},必须换思路。

关键观察:一次单点修改到底改变了什么? 看位置 PP 在最优方案中的处境:

  1. PP 未被标记:它只起断点作用,值是多少(TPT_P 还是 XX)完全不影响得分。 此时最优值 = 前缀 [1,P−1][1, P-1] 的最优 + 后缀 [P+1,N][P+1, N] 的最优 = f[P−1]+g[P+1]f[P-1] + g[P+1]。
  2. PP 被标记:它落在某个覆盖 PP 的标记区间 [a,b][a, b] 中。把 TPT_P 改成 XX 只让 这一个区间的元素和增加 X−TPX - T_P,于是总得分恰好减少 X−TPX - T_P,其余部分的决策不受影响。

所以若定义 B[P]B[P] = 在原序列中强制标记 PP 时的最大总得分,那么 PP 被标记时的答案 就是 B[P]−X+TPB[P] - X + T_P。而因为标记区间互不相交,覆盖 PP 的区间至多一个,两种情况穷尽了所有 方案:

ans(P,X)=max⁡(f[P−1]+g[P+1]⏟与 X 无关,  B[P]−X+TP⏟与 X 线性相关)\mathrm{ans}(P, X) = \max\Big( \underbrace{f[P-1] + g[P+1]}_{\text{与 } X \text{ 无关}},\; \underbrace{B[P] - X + T_P}_{\text{与 } X \text{ 线性相关}} \Big)

动态询问就这样被压成了纯静态预处理——只要算出 f,g,Bf, g, B 三个数组,每次询问 O(1)O(1)。

求 ff 与 gg(斜率优化)。 把转移式里的交叉项拆出来:

f[i]=max⁡(f[i−1],  i2+i2−Si+max⁡0≤m<i{cm−i⋅m}),cm=f[m−1]+Sm+m(m−1)2f[i] = \max\left(f[i-1],\; \tfrac{i^2+i}{2} - S_i + \max_{0 \le m < i}\big\{ c_m - i \cdot m \big\}\right),\qquad c_m = f[m-1] + S_m + \tfrac{m(m-1)}{2}

内层就是对直线 y=mx+cmy = m x + c_m 在 x=−ix = -i 处取最大值。mm 随 ii 递增而递增, x=−ix = -i 递减,维护斜率递增的上凸包即可,但查询点不单调——用二分查询,得 O(Nlog⁡N)O(N \log N)。 gg 完全对称:g[i]g[i] 表示后缀 i..Ni..N 的最优值,g[N+1]=0g[N+1] = 0,把区间右端写成 [i,j−1][i, j-1] 后 同样化为直线查询。

求 B[P]B[P](CDQ 分治 + 凸包)。 强制标记 PP 即要求区间 [a,b][a, b] 满足 a≤P≤ba \le P \le b, 此时左右两侧仍是独立的前缀/后缀问题,于是

B[P]=max⁡a≤P≤b(f[a−2]+(b−a+1)(b−a+2)2−(Sb−Sa−1)+g[b+2])B[P] = \max_{a \le P \le b}\Big( f[a-2] + \tfrac{(b-a+1)(b-a+2)}{2} - (S_b - S_{a-1}) + g[b+2] \Big)

把区间贡献展开并按 aa、bb 分离((b−a+1)(b−a+2)2\dfrac{(b-a+1)(b-a+2)}{2} 里含交叉项 abab):

f[a−2]+((b−a+1)(b−a+2)2−(Sb−Sa−1))+g[b+2]=leftPart[a]+rightPart[b]−a⋅bf[a-2] + \Big(\tfrac{(b-a+1)(b-a+2)}{2} - (S_b - S_{a-1})\Big) + g[b+2] = \text{leftPart}[a] + \text{rightPart}[b] - a \cdot b
leftPart[a]=f[a−2]+Sa−1+a2−3a2,rightPart[b]=g[b+2]−Sb+b2+3b+22\text{leftPart}[a] = f[a-2] + S_{a-1} + \tfrac{a^2 - 3a}{2},\qquad \text{rightPart}[b] = g[b+2] - S_b + \tfrac{b^2 + 3b + 2}{2}

(a≤2a \le 2 时 f[a−2]f[a-2] 视为 00,b≥N−1b \ge N-1 时 g[b+2]g[b+2] 视为 00。)

现在的任务变成:对每个 PP 求 max⁡{leftPart[a]+rightPart[b]−ab:a≤P≤b}\max\{ \text{leftPart}[a] + \text{rightPart}[b] - ab : a \le P \le b \}。 直接做是 O(N2)O(N^2)。用 CDQ 分治(分治下标区间 [lo,hi][lo, hi],midmid 为中点):

  • 更新左半边 P∈[lo,mid]P \in [lo, mid]:条件 a≤Pa \le P,而只要 b≥mid+1b \ge mid+1 就自动有 b≥Pb \ge P。 于是对每个 aa 只需在右半边 b∈[mid+1,hi]b \in [mid+1, hi] 的凸包里查 max⁡(rightPart[b]−ab)\max(\text{rightPart}[b] - a b), 得到 val(a)val(a);再对 valval 做前缀最大值(把 a≤Pa \le P 内的所有 aa 都取到), 一次性覆盖左半边所有 PP。
  • 更新右半边 P∈[mid+1,hi]P \in [mid+1, hi]:对称地,对每个 bb 在左半边 aa 的凸包里查 max⁡(leftPart[a]−ab)\max(\text{leftPart}[a] - a b),得 val′(b)val'(b),再做后缀最大值覆盖右半边所有 PP。

两边的凸包斜率与查询 xx 都单调,指针扫描即可 O(区间长)O(\text{区间长})。每层总长 O(N)O(N), 共 O(log⁡N)O(\log N) 层,总复杂度 O(Nlog⁡N)O(N \log N)。

代码

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-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()
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-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;
}

复杂度

时间 O(Nlog⁡N+M)O(N \log N + M):斜率优化 DP O(Nlog⁡N)O(N \log N),CDQ 分治 O(Nlog⁡N)O(N \log N),询问 O(1)O(1); 空间 O(N)O(N)。最大点 N=M=3×105N = M = 3 \times 10^5 时,C++ 实测最慢 0.40.4 s(峰值内存 24 MB), Python 同阶但常数较大,实测约 2.52.5 s。

总结

本题的核心是把「单点修改 + 询问最优值」的在线问题转成离线预处理:只要观察到修改值 XX 只通过 ±(X−TP)\pm(X - T_P) 影响得分,且是否覆盖 PP 只有两种互斥情形,就能把 XX 从 DP 中剖出去, 留下三个与 XX 无关的静态数组。剩下的是两次斜率优化加一次「区间包含约束下的二维最值」, 后者正是 CDQ 分治 + 凸包的经典形状——a≤P≤ba \le P \le b 被中点劈成两段条件,各退化成一次 单调凸包扫描。

与前缀 DP 相比,B[P]B[P] 多出来的是 a,ba, b 两侧独立的乘积项,这使权矩阵成为反 Monge 矩阵, 也是分治能成立的结构性原因。

实现上要注意两点:c(c+1)2\tfrac{c(c+1)}{2} 在 N=3×105N = 3 \times 10^5 时可达 4.5×10104.5 \times 10^{10}, 凸包叉积涉及 1012×10510^{12} \times 10^{5} 量级,C++ 用 __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 求后缀最大值"]