鏖战字符串

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

两种删除代价分别优化:代价①是二次型用斜率优化维护下凸壳,代价②的合法分割点构成随 i 单调右移的连续区间,用双指针加单调队列求区间最小值,总复杂度 O(n)。

OJ: roj

题目 ID: 1793

难度:提高+/省选-

标签:动态规划斜率优化单调队列双指针python

创建: 2026-10-08 03:33

更新: 2026-10-08 03:33

形式化题目

给定长度 nn 的小写字母串 ss 与权值 dif[1..n]dif[1..n],以及常数 a,b,c,d,l,ra, b, c, d, l, r。 对每个 i∈[1,n]i \in [1, n],把前缀 [1,i][1, i] 切成若干连续子串 s[j1+1..j2],s[j2+1..j3],…s[j_1+1..j_2], s[j_2+1..j_3], \dots, 每个子串独立地二选一删除,代价为

cost(p,q)=min⁡(a⋅X2+b,    [ m(p,q)∈[l,r] ]⋅(c⋅X+d)),X=∑k=pqdif[k], \text{cost}(p, q) = \min\Bigl( a \cdot X^2 + b,\;\; [\,m(p,q) \in [l, r]\,] \cdot (c \cdot X + d) \Bigr), \qquad X = \sum_{k=p}^{q} dif[k],

其中 m(p,q)m(p, q) 是子串 s[p..q]s[p..q] 中出现次数最多的字符的出现次数, [⋅][\cdot] 为真值指示函数(条件不成立时该项不可用)。求

f[i]=min⁡0=j0<j1<⋯<jk=i∑tcost(jt−1+1, jt), f[i] = \min_{0 = j_0 < j_1 < \cdots < j_k = i} \sum_{t} \text{cost}(j_{t-1}+1,\, j_t),

即删去每个前缀 [1,i][1, i] 的最少用时。

因为 ∑\sum 的代价可加、切分点顺序无关,这天然是一条线性 DP:

f[0]=0,f[i]=min⁡0≤j<i{f[j]+cost(j+1,i)}. f[0] = 0, \qquad f[i] = \min_{0 \le j < i} \Bigl\{ f[j] + \text{cost}(j+1, i) \Bigr\}.

记 pre[i]=∑k≤idif[k]pre[i] = \sum_{k \le i} dif[k](pre[0]=0pre[0] = 0),则子串 s[j+1..i]s[j+1..i] 的难度之和恒为 pre[i]−pre[j]pre[i] - pre[j]。

正解

思路

先看朴素 DP 的瓶颈。 直接按上面的转移式做,对每个 ii 枚举 j∈[0,i−1]j \in [0, i-1], 再统计子串 s[j+1..i]s[j+1..i] 的字符频次。倒序枚举 jj 并增量维护频次可以把单点代价压到 O(1)O(1), 但"枚举 jj"这一层无法省掉,总复杂度 O(n2)O(n^2);n≤105n \le 10^5 时是 101010^{10} 量级的操作,必然超时。

关键想法:两种删除方式的结构完全不同,把它们拆开、各自用最合适的数据结构求最小值。 即分别求出

f1[i]=min⁡0≤j<i{f[j]+a(pre[i]−pre[j])2+b},f2[i]=min⁡j∈Ji{f[j]+c(pre[i]−pre[j])+d}, f_1[i] = \min_{0 \le j < i} \bigl\{ f[j] + a (pre[i] - pre[j])^2 + b \bigr\}, \qquad f_2[i] = \min_{j \in J_i} \bigl\{ f[j] + c (pre[i] - pre[j]) + d \bigr\},

其中 Ji={ j:m(j+1,i)∈[l,r] }J_i = \{\, j : m(j+1, i) \in [l, r] \,\} 是方法②可用的分割点集合,最后取 f[i]=min⁡(f1[i],f2[i])f[i] = \min(f_1[i], f_2[i])。

方法①:二次型代价 → 斜率优化。 展开转移式:

f[j]+a(pre[i]−pre[j])2+b=(a⋅pre[i]2+b)+(f[j]+a⋅pre[j]2)−2a⋅pre[i]⋅pre[j]. f[j] + a (pre[i] - pre[j])^2 + b = \bigl( a \cdot pre[i]^2 + b \bigr) + \bigl( f[j] + a \cdot pre[j]^2 \bigr) - 2a \cdot pre[i] \cdot pre[j].

固定 ii,前一项是常量,于是要最小化的是一个点积。把每个决策点 jj 看成平面上的点

Xj=pre[j],Yj=f[j]+a⋅pre[j]2, X_j = pre[j], \qquad Y_j = f[j] + a \cdot pre[j]^2,

则 f1[i]=a⋅pre[i]2+b+min⁡j(Yj−KiXj)f_1[i] = a \cdot pre[i]^2 + b + \min_j \bigl( Y_j - K_i X_j \bigr),其中查询斜率 Ki=2a⋅pre[i]K_i = 2a \cdot pre[i]。

由于 dif[k]≥0dif[k] \ge 0,前缀和 prepre 单调不减,所以插入点的横坐标 XjX_j 与查询斜率 KiK_i 都单调不减。 这正是斜率优化(维护下凸壳)的标准形态:用单调队列维护下凸壳,队头就是当前 KiK_i 下的最优决策点, 均摊 O(1)O(1) 查一次。

一个必须处理的坑:dif[i]dif[i] 可以取 00,此时 pre[j]=pre[j−1]pre[j] = pre[j-1],两个决策点的横坐标重合。 直接用 Yq−YpXq−Xp\dfrac{Y_q - Y_p}{X_q - X_p} 判凸性会除零;而且同横坐标的点只有 YY 最小的那个有意义。 实现里一律用交叉相乘判斜率(longlonglong long 乘法升到 __int128 防溢出), 并在入队前先对同横坐标去重。

方法②:条件本身有单调性 → 双指针 + 单调队列。 把转移式展开:

f[j]+c(pre[i]−pre[j])+d=(f[j]−c⋅pre[j])+c⋅pre[i]+d. f[j] + c (pre[i] - pre[j]) + d = \bigl( f[j] - c \cdot pre[j] \bigr) + c \cdot pre[i] + d.

只要 jj 合法,贡献项 h(j)=f[j]−c⋅pre[j]h(j) = f[j] - c \cdot pre[j] 与 ii 无关。难点全部落在"哪些 jj 合法"上。

固定右端点 ii,让左端点从 ii 往左走(子串变长),窗口内的字符只增不减,所以

m(j+1,i) 关于 j 单调不增. m(j+1, i) \text{ 关于 } j \text{ 单调不增}.

于是:

  • "最大频次 ≤r\le r"要求窗口足够短 ⇒ 合法的 jj 是一段后缀 j≥Lij \ge L_i;
  • "最大频次 ≥l\ge l"要求窗口足够长 ⇒ 合法的 jj 是一段前缀 j≤Rij \le R_i。

两者相交,Ji=[Li,Ri]J_i = [L_i, R_i] 是一段连续区间(可能为空——例如 l>rl > r 时恒为空,方法② 自动失效)。

而且 Li,RiL_i, R_i 都随 ii 单调不减:新字符加入只会让频次增加,为了压制频次(或达到频次), 左端点只能往右挪。具体地,设 cntccnt_c 为字符 cc 到目前位置为止的出现次数, posc(k)pos_c(k) 为 cc 第 kk 次出现的位置,则有

Ri=max⁡c posc(cntc−l+1)−1,Li=max⁡c(posc(cntc−r), 0), R_i = \max_c \, pos_c\bigl(cnt_c - l + 1\bigr) - 1, \qquad L_i = \max_{c}\Bigl( pos_c\bigl(cnt_c - r\bigr),\ 0 \Bigr),

每一项都是"某个字符第固定次数出现的位置",随 ii 只增不减,取 max⁡\max 后仍单调不减。

于是问题变成:在左右端点都单调不减的滑动窗口 [Li,Ri][L_i, R_i] 上反复求 h(j)h(j) 的最小值。 这就是单调队列的标准场景:右端点右移时把新决策点从队尾推入(维持 hh 递增), 左端点右移时把队头过期的弹掉,队头即答案。

两种方法的合并。 每个 ii 先取凸壳给出的 f1[i]f_1[i],再判断方法②的窗口 [Li,Ri][L_i, R_i] 是否非空; 非空则用队头算 f2[i]f_2[i] 并取较小值。注意 l>rl > r 时区间恒空,程序必须能自然地退化到纯方法①, 不能从空队列里取值。

小规模手算样例。 样例为 n=5n = 5、a=1,b=3,c=1,d=5,l=1,r=1a=1,b=3,c=1,d=5,l=1,r=1、s=abwads = \texttt{abwad}、difdif 全 11, 故 pre=(0,1,2,3,4,5)pre = (0,1,2,3,4,5),方法②需要子串恰好有 1 个出现次数为 1 的"最高频字符"(即所有字符互不相同)。

ii 方法①最优 jj f1[i]f_1[i] 方法②可用 jj 集合 方法②最优 jj f2[i]f_2[i] f[i]f[i]
1 0 0+12+3=40 + 1^2 + 3 = 4 {0}\{0\}(a 出现 1 次) 0 0+1+5=60 + 1 + 5 = 6 4
2 0 0+22+3=70 + 2^2 + 3 = 7 {0,1}\{0, 1\} 0 0+2+5=70 + 2 + 5 = 7 7
3 2 7+12+3=117 + 1^2 + 3 = 11 {0,1,2}\{0,1,2\}(bwa 互不相同) 0 0+3+5=80 + 3 + 5 = 8 8
4 3 8+12+3=128 + 1^2 + 3 = 12 {1,2,3}\{1,2,3\} 1 4+3+5=124 + 3 + 5 = 12 12
5 3 8+22+3=158 + 2^2 + 3 = 15 {1,2,3,4}\{1,2,3,4\} 1 4+4+5=134 + 4 + 5 = 13 13

第 4 行是双指针必须小心的地方:abwad 里 a 出现 2 次,j=0j = 0 已经因 “最大频次 ≤r=1\le r = 1” 被淘汰,合法集合只剩 {1,2,3}\{1,2,3\}(即左端点的下界 L4=1L_4 = 1);方法② 给出的 1212 与方法① 恰好打平, 所以 f[4]=12f[4] = 12 有多条最优路径(j=3j=3 的方法① 与 j=1j=1 的方法②)。最后 i=5i = 5 用的正是题面提示的那条: j=1j = 1 时左串 s[1..1]=as[1..1] = \texttt{a} 用方法① 删(1×1+3=41\times1+3=4), 右串 s[2..5]=bwads[2..5] = \texttt{bwad} 用方法② 删(1×4+5=91\times4+5=9),合计 4+9=134 + 9 = 13。

代码

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-08 03:30
# update_at: 2026-10-08 03:30

import sys
from collections import deque

HULL_NEED = 2  # 下凸壳至少留几个点才能判断中间点冗余

type IndexQueue = deque[int]  # 决策点下标队列:方法① 的凸壳与方法② 的滑动窗口各用一个


def delete_costs(n: int, a: int, b: int, c: int, d: int, lmin: int, rmax: int,
                 s: bytes, dif: list[int]) -> list[int]:
    """依次算出删去每个前缀 [1,i] 的最少用时:返回长度 n 的答案表 dp[1..n]。

    方法①(代价 a*x^2+b)用斜率优化维护下凸壳;方法②(代价 c*x+d)的合法分割点构成
    随 i 单调右移的连续区间,用双指针维护区间端点、单调队列取区间内最小值。
    """
    pre = [0] * (n + 1)                                  # pre[i] = 前缀 [1,i] 的删除难度之和
    for i in range(1, n + 1):
        pre[i] = pre[i - 1] + dif[i - 1]                 # dif >= 0,故 pre 单调不减

    dp = [0] * (n + 1)                                   # dp[i] = 删去前缀 [1,i] 的最少用时
    occ: list[list[int]] = [[] for _ in range(26)]       # occ[ch] = 字符 ch 出现位置的升序表
    hull: IndexQueue = deque()                           # 下凸壳上的决策点下标
    window: IndexQueue = deque()                         # 合法区间内 h(j) 递增的决策点下标

    def yval(j: int) -> int:
        """方法① 凸壳上决策点 j 的纵坐标 dp[j] + a*pre[j]^2。"""
        return dp[j] + a * pre[j] * pre[j]

    def hvalue(j: int) -> int:
        """方法② 中与右端点无关的贡献 dp[j] - c*pre[j]。"""
        return dp[j] - c * pre[j]

    def hull_push(j: int) -> None:
        """把决策点 j 压入方法① 的下凸壳(横坐标重合时只留纵坐标更小者)。"""
        xj = pre[j]
        if hull and pre[hull[-1]] == xj:                 # dif 含 0 时横坐标会重合,凸壳不能带重复 x
            if yval(hull[-1]) <= yval(j):
                return
            hull.pop()
        while len(hull) >= HULL_NEED:
            p, q = hull[-2], hull[-1]
            # 下凸壳约定:slope(p,q) >= slope(q,j) 说明 q 在弦上方,应丢弃。
            # 交叉相乘代替除法,避免 dif=0 时除零,也避免浮点误差。
            q_redundant = (yval(q) - yval(p)) * (xj - pre[q]) >= (yval(j) - yval(q)) * (pre[q] - pre[p])
            if not q_redundant:
                break
            hull.pop()
        hull.append(j)

    def hull_best(k: int) -> int:
        """在查询斜率 k = 2a*pre[i] 下取最优决策点;k 单调不减,队头只往前移。"""
        while len(hull) >= HULL_NEED:
            j0, j1 = hull[0], hull[1]
            # 队头不如第二个点时就弹掉队头(k 递增,被弹掉的不会再变好)
            front_worse = yval(j0) - k * pre[j0] >= yval(j1) - k * pre[j1]
            if not front_worse:
                break
            hull.popleft()
        return hull[0]

    sL = sR = 0      # 方法② 的合法决策区间固定是 [sR, sL-1],两个端点都随 i 单调不减
    pushed = -1      # window 中已经推入的最大下标
    ans: list[int] = []

    for i in range(1, n + 1):
        ch = s[i - 1] - 97                               # 当前字符
        occ[ch].append(i)
        cnt = len(occ[ch])
        # 第 (cnt-lmin+1) 次出现的位置:左端点取它时窗口内 ch 恰有 lmin 个 => maxfreq >= lmin
        if cnt >= lmin:
            sL = max(sL, occ[ch][cnt - lmin])
        # 第 (cnt-rmax) 次出现的位置:左端点越过它后 ch 就超过 rmax 个 => maxfreq <= rmax
        if cnt > rmax:
            sR = max(sR, occ[ch][cnt - rmax - 1])

        while pushed < sL - 1:                           # 右端点单调不减,逐个把新决策点推进去
            pushed += 1
            hv = hvalue(pushed)
            while window and hvalue(window[-1]) >= hv:
                window.pop()
            window.append(pushed)
        while window and window[0] < sR:                 # 左端点单调不减,弹出过期决策点
            window.popleft()                             # lmin > rmax 时区间为空,队列被清空

        hull_push(i - 1)
        j1 = hull_best(2 * a * pre[i])                   # 方法①:凸壳上的最优分割点
        best = dp[j1] + a * (pre[i] - pre[j1]) ** 2 + b

        if window:                                       # 方法②:区间非空才可用
            j2 = window[0]
            cand = dp[j2] - c * pre[j2] + c * pre[i] + d
            if cand < best:
                best = cand

        dp[i] = best
        ans.append(best)
    return ans


def solve() -> None:
    # 输入是严格的三行结构:第一行 7 个整数、第二行字符串、第三行 n 个整数,按行读最直接。
    n, a, b, c, d, lmin, rmax = map(int, sys.stdin.buffer.readline().split())
    s = sys.stdin.buffer.readline().strip()               # 字符串行,取下标得 ASCII 码
    dif = list(map(int, sys.stdin.buffer.read().split()))
    print("\n".join(map(str, delete_costs(n, a, b, c, d, lmin, rmax, s, dif))))


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-08 03:30
 * update_at: 2026-10-08 03:30
 */

// 一本通 1793《鏖战字符串》
// 题意:给出长度 n 的字符串与每个位置的删除难度 dif[i](0 <= dif[i] <= 50)。
//   要把前缀 [1,i] 切成若干连续子串,每个子串二选一删除:
//     ① 代价 a*x^2 + b                    (x = 子串内 dif 之和)
//     ② 代价 c*x + d,当且仅当子串中出现次数最多的字符出现次数 ∈ [l, r]
//   求删去每个前缀 [1,i] 的最少用时,输出 n 行。
//
// 算法(O(n)):
//   pre[i] = sum_{k<=i} dif[k](因 dif >= 0,pre 单调不减),dp[0] = 0。
//   dp[i] = min_{0<=j<i} { dp[j] + cost(j+1, i) },
//   cost(j+1,i) = min( a*X^2 + b , [maxfreq(j+1,i) ∈ [l,r]] * (c*X + d) ),X = pre[i]-pre[j]。
//
//   (A) 方法① —— 斜率优化(下凸壳):
//       dp[j] + a*(pre[i]-pre[j])^2 + b = a*pre[i]^2 + b + ( dp[j] + a*pre[j]^2 ) - 2a*pre[i]*pre[j]
//       点 (X_j, Y_j) = (pre[j], dp[j] + a*pre[j]^2),查询斜率 K_i = 2a*pre[i]。
//       X_j 与 K_i 都随 i 单调不减 => 维护下凸壳 + 单调队列,均摊 O(1) 查一次。
//
//   (B) 方法② —— 频次窗口 + 滑动窗口最小值:
//       固定 i,maxfreq(j+1, i) 随 j 增大单调不增(窗口变短)。
//       于是「maxfreq >= l」的 j 构成前缀 j <= sL-1,「maxfreq <= r」的 j 构成后缀 j >= sR,
//       合法集合是连续区间 [sR, sL-1](l > r 时为空,方法② 自动失效,退化为纯 (A))。
//       sL = max_c ( 字符 c 第 (cnt_c-l+1) 次出现的位置 ),sR = max_c ( 第 (cnt_c-r) 次出现的位置,不足取 0 );
//       两者都随 i 单调不减,故 [sR, sL-1] 是双指针维护的滑动窗口。
//       区间内最小化 dp[j] - c*pre[j](与 i 无关)用单调队列,均摊 O(1)。
//
//   复杂度 O(n) 时间、O(n) 空间。中间量最大约 233 * (50*1e5)^2 ≈ 5.8e15,long long 安全。
//   dif[i] = 0 时会出现 pre[j] == pre[j-1](横坐标重合),凸壳入队时单独去重,不能直接除斜率。

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef __int128 lll;

const int MAXN = 100005;

ll n;              // 字符串长度
ll A, B, C, D;     // 题面的 a, b, c, d
ll LNEED, RNEED;   // 题面的 l, r
char str_[MAXN];   // 字符串,1-based
ll dif[MAXN];      // dif[i]:第 i 个字符的删除难度
ll pre[MAXN];      // pre[i]:前缀 [1,i] 的删除难度之和
ll dp[MAXN];       // dp[i]:删去前缀 [1,i] 的最少用时

int occ[26][MAXN]; // occ[ch][k]:字符 ch 第 k 次出现的位置(1-based,k 从 1 开始)
int cnt[26];       // cnt[ch]:字符 ch 到目前为止的出现次数

// ---- 方法①:斜率优化(下凸壳)用的单调队列,存决策点下标 j ----
int hull[MAXN];
int hh, ht;        // 凸壳区间为 [hh, ht)

// 凸壳上决策点 j 的纵坐标 Y_j = dp[j] + a*pre[j]^2
ll yval(int j) {
    return dp[j] + A * pre[j] * pre[j];
}

// 下凸壳维护:slope(p,q) >= slope(q,r) 时 q 冗余(交叉相乘,避免除法与浮点误差)
bool hull_bad(int p, int q, int r) {
    lll lhs = (lll)(yval(q) - yval(p)) * (pre[r] - pre[q]);
    lll rhs = (lll)(yval(r) - yval(q)) * (pre[q] - pre[p]);
    return lhs >= rhs;
}

// 把决策点 j 插入下凸壳
void hull_add(int j) {
    if (ht > hh && pre[hull[ht - 1]] == pre[j]) { // 横坐标重合(dif 出现 0),只留 Y 更小者
        if (yval(hull[ht - 1]) <= yval(j)) return;
        ht--;
    }
    while (ht - hh >= 2 && hull_bad(hull[ht - 2], hull[ht - 1], j)) ht--;
    hull[ht++] = j;
}

// 查询斜率 K 下的最优决策点;K 随 i 单调不减,队头只往后走,均摊 O(1)
int hull_best(ll K) {
    while (ht - hh >= 2) {
        int j0 = hull[hh], j1 = hull[hh + 1];
        if (yval(j0) - K * pre[j0] >= yval(j1) - K * pre[j1]) hh++;
        else break;
    }
    return hull[hh];
}

// ---- 方法②:滑动窗口最小值的单调队列,存下标 j,按 dp[j]-c*pre[j] 递增 ----
ll win[MAXN];
int wh, wt;

int main() {
    if (scanf("%lld %lld %lld %lld %lld %lld %lld", &n, &A, &B, &C, &D, &LNEED, &RNEED) != 7) return 0;
    scanf("%s", str_ + 1);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &dif[i]);
        pre[i] = pre[i - 1] + dif[i]; // dif >= 0,pre 单调不减
    }

    dp[0] = 0;
    ll sL = 0, sR = 0; // 合法决策区间为 [sR, sL-1]
    ll pushed = -1;    // win 中已推入的最大下标

    for (int i = 1; i <= n; i++) {
        int ch = str_[i] - 'a';
        cnt[ch]++;
        occ[ch][cnt[ch]] = i;

        // 更新 sL:字符 ch 第 (cnt-l+1) 次出现的位置,说明以它为左端点的窗口装得下 >= l 个 ch
        ll k1 = cnt[ch] - LNEED + 1;
        if (k1 >= 1 && occ[ch][k1] > sL) sL = occ[ch][k1];
        // 更新 sR:字符 ch 第 (cnt-r) 次出现的位置,左端点越过它后 ch 的出现次数必 <= r
        ll k2 = cnt[ch] - RNEED;
        if (k2 >= 1 && occ[ch][k2] > sR) sR = occ[ch][k2];

        // 右端点 sL-1 单调不减,逐个把新决策点推入单调队列
        while (pushed < sL - 1) {
            pushed++;
            ll hv = dp[pushed] - C * pre[pushed];
            while (wt > wh && dp[win[wt - 1]] - C * pre[win[wt - 1]] >= hv) wt--;
            win[wt++] = pushed;
        }
        // 左端点 sR 单调不减,弹出过期决策点(sR > sL-1 时队列会被清空,方法② 失效)
        while (wt > wh && win[wh] < sR) wh++;

        hull_add(i - 1);                    // 决策点 j = i-1 此刻的 dp 已确定,先入凸壳再查询
        int j1 = hull_best(2 * A * pre[i]); // 方法①的最优分割点
        ll best = dp[j1] + A * (pre[i] - pre[j1]) * (pre[i] - pre[j1]) + B;

        if (wt > wh) { // 方法②可用:区间 [sR, sL-1] 非空
            ll j2 = win[wh];
            ll cand = dp[j2] - C * pre[j2] + C * pre[i] + D;
            if (cand < best) best = cand;
        }

        dp[i] = best;
        printf("%lld\n", dp[i]);
    }
    return 0;
}

复杂度

  • 时间:前缀和 O(n)O(n);凸壳中每个决策点最多入队出队各一次,O(n)O(n); 双指针中 LiL_i、RiR_i 各单调右移最多 nn 次,O(n)O(n);方法②的单调队列同样 O(n)O(n)。 每次更新字符出现位置需要按字符维护位置列表,均摊 O(1)O(1)。总计 O(n)O(n), 常数很小,n=105n = 10^5 时实测在毫秒级(限时 1000 ms)。
  • 空间:prepre、ff、凸壳、单调队列、以及每个字符的出现位置(合计 nn 个),都是 O(n)O(n)。 C++ 侧约 n×3n \times 3 个 64 位整数加上位置表,实测峰值内存远低于 128 MB。
  • 数值范围:pre[i]≤50×105=5×106pre[i] \le 50 \times 10^5 = 5\times 10^6, 最大中间量 a⋅(pre[i]−pre[j])2≈233×(5×106)2≈5.8×1015a \cdot (pre[i]-pre[j])^2 \approx 233 \times (5\times 10^6)^2 \approx 5.8\times 10^{15}, 超过 32 位整数,必须用 64 位;凸壳判斜率时的交叉相乘再升一档到 __int128。

总结

  • 按代价的结构拆转移:同一个 DP 的两种转移如果形状不同(一个二次、一个线性), 不要硬塞进一个数据结构,拆开后各自可以用最简单的工具解决。
  • 斜率优化的两个单调性:入队点的横坐标单调、查询斜率单调,二者同时成立才能用单调队列维护凸壳; 本题由 dif≥0⇒predif \ge 0 \Rightarrow pre 单调不减保证。横坐标重合(dif[i]=0dif[i] = 0)时必须去重并用交叉相乘判凸性。
  • "合法决策点构成连续区间,且端点单调"是滑动窗口的标志:方法②的条件只跟子串内的频次有关, 窗口越长最大频次越大,于是合法 jj 天然是区间,且随着 ii 右移整体右移。
  • 不可用状态要能自然退化:l>rl > r 时方法② 恒不可用,双指针会让左端点越过右端点、 单调队列被清空,此时必须显式判断"区间非空"再取值。
  • 本题数据说明:素材源自带了数据生成脚本(data.py),说明本题的测试数据是自行构造的 (按题面分 10 个难度层次:边界、样例、小/中/大规模、全同字符、{a,b} 字符集、l > r 等), 原题(一本通·高手训练)的官方数据不可得;因此本文的结论只在"题面 + 这套数据"上经过验证, 与官方原题数据可能有差异。素材源的 std.cpp 与本解思路一致(同为凸壳 + 频次窗口,但写法不同), 编译后在 10 个真实点与数百组随机小数据上与本文两份实现逐字节一致,可以互相印证; 但两者都不等于官方标程。