P5426. 连续保留与深度量化

场次：2026年9月11日 · 来源：CodeFun2000 P5426

题目描述

端侧计算平台运行大模型时，需要在有限内存下做高性能推理，因此要对模型层做动态剪枝（Pruning）和量化（Quantization）。一层网络含 $N$ 个参数块，块 $i$ 有两个属性：

1. 重要度评分 $S_i$：该块对模型精度的贡献，分值越高越重要。
2. 内存占用 $M_i$：该块量化后的存储开销。

系统负载会动态变化。必须在总内存预算 $B$ 的约束下，选出一段连续的参数块加以保留（连续是为了保证访存局部性），使得保留段的重要度之和最大。

给定 $N$ 个参数块的属性以及当前内存预算 $B$，计算：

1. 在连续块总内存满足 $\sum M \le B$ 的前提下，能够得到的最大重要度之和。
2. 引入「位宽折损」：允许对当前选中连续段中最不重要的一个参数块做深度量化，其内存占用变为 $\lfloor M_i/2\rfloor$，重要度变为 $0$。若有多块重要度同为最小，则对其中内存占用最大的一块折损。此种机制下，最大重要度之和是多少？

输入格式

第一行两个正整数 $N$ 和 $B$，分别表示参数块数量与内存预算。

第二行 $N$ 个正整数，依次为各块重要度 $S_1, S_2, \ldots, S_N$。

第三行 $N$ 个正整数，依次为各块内存占用 $M_1, M_2, \ldots, M_N$。

数据范围：

$1\le N\le 10^5$

$1\le B\le 10^9$

$1\le S_i\le 10^4$，$1\le M_i\le 10^4$

输出格式

输出一行两个整数，以空格分隔：

第一个整数：常规连续剪枝下的最大重要度之和。

第二个整数：引入「位宽折损」后的最大重要度之和。

若没有任何合法连续段，对应值为 $0$。折损是可选项：一段已经满足 $\sum M \le B$ 的区间，也可以不折损。

示例

示例 1

输入：

4 13
80 15 80 15
6 3 6 3

输出：

110 160

说明：

1. 常规：保留 $[15,80,15]$，占用 $3+6+3=12\le 13$，重要度 $110$。另一段 $[80,15,80]$ 占用 $15>13$，不合法；$[80,15]$ 合法但重要度只有 $95$。
2. 折损：保留 $[80,15,80]$，对重要度为 $15$ 的块折损，占用变为 $6+\lfloor 3/2\rfloor+6=13\le 13$，重要度 $80+0+80=160$。

示例 2

输入：

5 12
8 16 24 32 40
5 6 7 4 3

输出：

72 72

说明：

1. 常规：保留最后两块 $[32,40]$，占用 $4+3=7\le 12$，重要度 $72$。$[24,32,40]$ 占用 $7+4+3=14>12$；$[24,32]$ 占用 $11$ 但重要度只有 $56$。
2. 折损：$[24,32,40]$ 中最不重要的是 $24$，占用变为 $\lfloor 7/2\rfloor+4+3=10\le 12$，重要度 $72$，不优于常规。$[16,24,32]$ 折损 $16$ 后占用 $\lfloor 6/2\rfloor+7+4=14>12$。

---

解题思路

第一步：理解问题本质

题目给了两组数：重要度 $S_i$、内存占用 $M_i$，要求选出一段连续的块，在内存预算 $B$ 下让重要度之和最大。两个问题只差一条规则：

1. 常规：段内内存之和 $\le B$；
2. 折损：段内允许把一块的内存变成 $\lfloor M_i/2\rfloor$、重要度变成 $0$，再要求内存之和 $\le B$。

先把折损这条规则翻译清楚：

• 折损哪一块不由我们挑，而是由区间唯一确定：区间内重要度最小的那块；重要度相同则取内存最大的那块；再相同则取下标最小的那块（否则同一个区间会有多种选择，答案不唯一）。
• 折损一块节省的内存是

  $$M_i-\left\lfloor\frac{M_i}{2}\right\rfloor=\left\lceil\frac{M_i}{2}\right\rceil$$

  折损一块损失的收益是 $S_i$。
• 折损是可选的：一段本来就放得下的区间，当然可以不放折损。

注意到两个关键条件：所有 $S_i>0$、所有 $M_i>0$。前者意味着“段越长收益越大”，后者意味着“段越长内存越大”。整个解法的两条单调性都来自这两点。

第二步：暴力解法

枚举所有区间 $[l,r]$，边向右扩展边维护三个量：内存和、重要度和、折损对象。因为区间只在一端扩展，折损对象可以增量更新：新元素和当前对象按 $(S, -M, \text{下标})$ 比大小即可，不需要每次重新扫一遍区间。

best_plain = 0
best_discount = 0

for l in range(n):
    total_m = 0
    total_s = 0
    target = -1          # 当前区间的折损对象
    for r in range(l, n):
        total_m += m[r]
        total_s += s[r]
        # 键更小者成为新的折损对象：重要度更小，或重要度相同但内存更大
        if target == -1 or (s[r], -m[r], r) < (s[target], -m[target], target):
            target = r

        if total_m <= budget:                    # 不放折损
            best_plain = max(best_plain, total_s)
            best_discount = max(best_discount, total_s)
        # 放折损：内存省下 ceil(M/2)，重要度丢掉 S_target
        if total_m - (m[target] + 1) // 2 <= budget:
            best_discount = max(best_discount, total_s - s[target])

每个左端点扫一遍右端点，共 $O(N^2)$ 个区间。$N=10^5$ 时约 $10^{10}$ 次操作，完全不可行，需要利用“正数”带来的单调性把区间枚举压成一条线。

第三步：优化解法——第一问的双指针

先只看第一问。固定右端点 $r$，观察左端点 $l$ 能取到多靠左：

• 内存和只增不减，所以合法左端点构成一个后缀 $[l(r),\,r]$，其中 $l(r)$ 是最靠左的合法左端点；
• 重要度和只增不减，而 $S_i>0$，所以 $[l(r),r]$ 是“以 $r$ 结尾的最优段”；
• 当 $r$ 右移一位时，$l(r)$ 不会变小：原来的 $[l(r),r]$ 已经尽量长了，再多一个元素只会让内存和更大。

于是左右两个指针都只往右走，一遍扫描 $O(N)$ 解决第一问：

left = 0
window_memory = 0
window_score = 0
best_plain = 0

for right in range(n):
    window_memory += memory[right]
    window_score += score[right]
    while window_memory > budget and left <= right:
        window_memory -= memory[left]
        window_score -= score[left]
        left += 1
    if left <= right:
        best_plain = max(best_plain, window_score)

第四步：最优解法——把“折损”也纳入窗口

第二问的难点在于：段内多了一个“特殊元素”（被折损的块），长度和内存之间的关系不再简单。解决它需要下面这个引理。

引理：记区间的有效内存为

$$Eff(l,r)=\sum_{k=l}^{r}M_k-\left\lceil\frac{M_{target}}{2}\right\rceil,$$

其中 $target$ 是该区间的折损对象。则往区间里再加一块时，$Eff$ 严格增大。

证明分两种情况。设原折损对象是 $o$，新加入的块是 $j$。

• $j$ 没有成为新的折损对象：省下来的内存还是原来那块，总内存多了 $M_j$，于是

  $$\Delta Eff=M_j>0.$$

• $j$ 成了新的折损对象：原来省 $\lceil M_o/2\rceil$，现在省 $\lceil M_j/2\rceil$，总内存多了 $M_j$，于是

  $$\Delta Eff=M_j+\left\lceil\frac{M_o}{2}\right\rceil-\left\lceil\frac{M_j}{2}\right\rceil =\left\lfloor\frac{M_j}{2}\right\rfloor+\left\lceil\frac{M_o}{2}\right\rceil>0.$$

两种情况下 $Eff$ 都严格增大，引理成立。

这个引理直接带来两个结论：

1. 可行区间对“扩张”封闭：$[l,r]$ 不可行，那么任何包含它的更大区间也不可行。所以左端点 $l(r)$ 仍然随 $r$ 单调右移，双指针依然成立。
2. 对固定的 $r$，最靠左的可行左端点最优。因为折损后的价值

   $$V(l,r)=\sum_{k=l}^{r}S_k-S_{target}$$

   也随扩张严格增大：若 $target$ 不变，价值增加 $S_j>0$；若 $j$ 成为新对象，价值增加 $S_o>0$（旧对象的重要度不再被扣除，新对象的重要度本来就要扣掉）。

剩下的问题是怎么在 $O(1)$ 内拿到窗口的折损对象。折损对象就是窗口内键 $(S_i,\,-M_i,\,i)$ 最小的元素，这是标准的“滑动窗口最小值”，用单调队列维护：

• 右端点进入时，弹掉队尾所有键不小于它的元素 —— 它们比新元素差，又会先离开窗口，永远不会再成为答案；
• 左端点离开时，如果它正好是队首，就 popleft()。

于是第二问也是 $O(N)$。最后别忘了折损是可选项，把答案初始化为第一问的结果。

---

完整代码实现

"""
P5426. 连续保留与深度量化 - 双指针 + 单调队列
"""

import sys
from collections import deque


def solve():
    """读入参数块信息，分别计算常规剪枝与允许折损后的最大重要度之和。"""
    data = sys.stdin.buffer.read().split()
    if not data:
        return

    it = iter(data)
    n = int(next(it))
    budget = int(next(it))
    score = [int(next(it)) for _ in range(n)]
    memory = [int(next(it)) for _ in range(n)]

    # ---------- 第一问：滑动窗口求“内存和 <= B 的最大重要度和” ----------
    best_plain = 0
    left = 0
    window_memory = 0
    window_score = 0
    for right in range(n):
        window_memory += memory[right]
        window_score += score[right]

        # 收缩到内存不超预算为止；若单块就超预算，窗口会被收成空的
        while window_memory > budget and left <= right:
            window_memory -= memory[left]
            window_score -= score[left]
            left += 1

        # 窗口非空时，它就是“以 right 结尾的最优合法段”：
        # 所有重要度都是正的，再往左扩只会更赚，扩不动才是最优。
        if left <= right and window_score > best_plain:
            best_plain = window_score

    # ---------- 第二问：把“折损对象”也纳入滑动窗口 ----------
    # 折损对象的排序键：重要度最小，其次内存最大，最后下标最小（保证唯一）。
    keys = [(score[i], -memory[i], i) for i in range(n)]

    best_discount = best_plain  # 折损是可选项，至少不会比常规方案差
    left = 0
    window_memory = 0
    window_score = 0
    # 单调队列：队首是当前窗口内键最小的元素，也就是折损对象
    min_queue = deque()

    for right in range(n):
        window_memory += memory[right]
        window_score += score[right]

        # 新元素入队前，弹掉队尾键不小于它的元素：
        # 它们既比新元素“差”，又会比新元素先离开窗口，以后不可能再成为折损对象。
        key_right = keys[right]
        while min_queue and keys[min_queue[-1]] >= key_right:
            min_queue.pop()
        min_queue.append(right)

        while min_queue:
            target = min_queue[0]
            # 折损 target 之后，这段区间实际占用的内存
            effective = window_memory - (memory[target] + 1) // 2
            if effective <= budget:
                break
            # 仍然超预算，只能把左端点右移（Eff 关于扩张严格递增，不会漏解）
            window_memory -= memory[left]
            window_score -= score[left]
            if min_queue[0] == left:
                min_queue.popleft()
            left += 1

        if min_queue:
            # 窗口非空，且价值关于扩张严格递增，当前窗口就是最优段
            target = min_queue[0]
            candidate = window_score - score[target]
            if candidate > best_discount:
                best_discount = candidate

    print(best_plain, best_discount)


if __name__ == "__main__":
    solve()

NumPy 版本

以下版本使用 NumPy。只有在评测环境允许第三方库时才能提交；CodeFun2000 的普通 Python 环境不一定安装 NumPy。

思路与纯 Python 版完全一致，只是把三处顺序逻辑换成了批量运算：内存前缀和、重要度前缀和都用 np.cumsum 一次算完；第一问的「最靠左的合法左端点」用 np.searchsorted 对全部右端点同时二分；第二问的折损对象改成「把键压成秩，用稀疏表做 $O(1)$ 区间最小值」，再让全部右端点同时二分左端点。代码里没有 $10^5$ 次量级的 Python 循环。

"""
P5426. 连续保留与深度量化 - NumPy 版

与纯 Python 版的双指针 + 单调队列等价，但把顺序逻辑换成向量化写法：
- 前缀和用 np.cumsum 一次算完；
- 第一问的“最靠左的合法左端点”用 np.searchsorted 在内存前缀和上二分，一次求出全部右端点；
- 第二问需要“区间内键最小的元素”，用稀疏表（ST 表）做 O(1) 区间最小值查询，
  再让所有右端点同时二分左端点，Python 层面只剩 log N 轮向量化比较。

时间复杂度：O(N log N)；空间复杂度：O(N log N)。
"""

import sys

import numpy as np


def build_sparse_table(rank):
    """st[k][i] 表示区间 [i, i + 2^k) 内 rank 最小的下标。

    键 (S_i, -M_i, i) 里带了下标，任意两个键都不相等，所以不用处理并列。
    """
    n = rank.size
    levels = max(1, n.bit_length())
    st = np.empty((levels, n), dtype=np.int64)
    st[0] = np.arange(n)

    k = 1
    while (1 << k) <= n:
        width = 1 << k
        half = width >> 1
        prev = st[k - 1]
        # 右半块不越界的位置才能用两个长度 2^(k-1) 的块拼成长度 2^k
        limit = n - width + 1
        left_idx = prev[:limit]
        right_idx = prev[half:half + limit]
        cur = prev.copy()
        cur[:limit] = np.where(rank[right_idx] < rank[left_idx], right_idx, left_idx)
        st[k] = cur
        k += 1

    # 未用到的层级填成“自己指自己”，避免读到未初始化内存
    for level in range(k, levels):
        st[level] = st[0]
    return st


def solve():
    data = sys.stdin.buffer.read().split()
    if not data:
        return

    n = int(data[0])
    budget = int(data[1])
    values = np.array(list(map(int, data[2:2 + 2 * n])), dtype=np.int64)
    score = values[:n]
    memory = values[n:2 * n]

    # ---------- 前缀和：pref_m[r] = M_0 + ... + M_{r-1} ----------
    pref_m = np.zeros(n + 1, dtype=np.int64)
    np.cumsum(memory, out=pref_m[1:])
    pref_s = np.zeros(n + 1, dtype=np.int64)
    np.cumsum(score, out=pref_s[1:])

    # ---------- 第一问：内存和 <= B 的最大重要度和 ----------
    # 对右端点 r 要最靠左的 l 使 pref_m[r+1] - pref_m[l] <= B，即 pref_m[l] >= pref_m[r+1] - B。
    # 内存都是正的，pref_m 严格递增，np.searchsorted 一次给出全部右端点的答案。
    right = np.arange(n)
    left_plain = np.searchsorted(pref_m, pref_m[1:] - budget, side="left")
    valid_plain = left_plain <= right                  # 单块就超预算的右端点没有合法窗口
    window_sum = pref_s[1:] - pref_s[left_plain]
    best_plain = int(window_sum[valid_plain].max()) if valid_plain.any() else 0

    # ---------- 第二问：把“折损对象”纳入区间 ----------
    # 折损对象 = 键 (S_i, -M_i, i) 最小的元素；把键压成“秩”，区间最小值就是秩最小的下标
    order = np.lexsort((right, -memory, score))
    rank = np.empty(n, dtype=np.int64)
    rank[order] = right

    sparse = build_sparse_table(rank)
    save = (memory + 1) // 2                           # 折损一块省下的内存 ceil(M/2)

    def window_target(left, right_end):
        """区间 [left, right_end] 内键最小的下标（两个参数是等长数组）。"""
        length = right_end - left + 1
        level = np.floor(np.log2(length)).astype(np.int64)
        span = np.left_shift(1, level)
        head = sparse[level, left]
        tail = sparse[level, right_end - span + 1]
        return np.where(rank[tail] < rank[head], tail, head)

    def effective(left, right_end):
        """折损 target 之后，区间 [left, right_end] 实际占用的内存。"""
        return pref_m[right_end + 1] - pref_m[left] - save[window_target(left, right_end)]

    # 区间只有一块时有效内存是 floor(M/2)：这一步都不满足的右端点根本没有合法窗口
    single_ok = (memory >> 1) <= budget

    # Eff 关于区间扩张严格递增 => 对固定右端点它关于左端点严格递减，
    # 于是“Eff <= B”在左端点上单调，可以二分。所有右端点同时二分。
    low = np.zeros(n, dtype=np.int64)
    high = right.copy()                                # high 处已知可行
    while True:
        pending = single_ok & (low < high)
        if not pending.any():
            break
        mid = ((low + high) >> 1)[pending]
        feasible = effective(mid, right[pending]) <= budget
        # 只有 pending 的元素会动，其余保持原值
        new_low = low.copy()
        new_high = high.copy()
        new_high[pending] = np.where(feasible, mid, high[pending])
        new_low[pending] = np.where(feasible, low[pending], mid + 1)
        low, high = new_low, new_high

    best_discount = best_plain                         # 折损可选，至少不比常规方案差
    if single_ok.any():
        ends = right[single_ok]
        starts = low[single_ok]
        candidate = pref_s[ends + 1] - pref_s[starts] - score[window_target(starts, ends)]
        best_discount = max(best_discount, int(candidate.max()))

    print(best_plain, best_discount)


if __name__ == "__main__":
    solve()

---

示例推演

样例 1

$N=4$、$B=13$：

块	0	1	2	3
重要度 $S$	80	15	80	15
内存 $M$	6	3	6	3

第一问（双指针）：

右端点 $r$	窗口	内存和	重要度和	说明
0	$[0,0]$	6	80	合法，最优 80
1	$[0,1]$	9	95	合法，最优 95
2	$[1,2]$	9	95	加入块 2 后内存 $15$ 超预算，左端点右移一格
3	$[1,3]$	12	110	合法，最优 110

第一问答案是 $110$。

第二问（带上折损对象）：

右端点 $r$	窗口	内存和	折损对象	有效内存	折损后重要度
0	$[0,0]$	6	块 0（$S=80$）	$6-3=3$	$80-80=0$
1	$[0,1]$	9	块 1（$S=15$）	$9-2=7$	$95-15=80$
2	$[0,2]$	15	块 1（$S=15$）	$15-2=13\le13$	$175-15=160$
3	$[1,3]$	12	块 1（$S=15$）	$12-2=10$	$110-15=95$

右端点 $r=3$ 时，若保留 $[0,3]$，内存 $18$、有效内存 $18-2=16>13$ 不合法，所以左端点右移一格；右移后内存 $12$、有效内存 $10$，重要度 $110-15=95$。

第二问取最大值 $\max(160,\,95,\,110)=160$，与第一问的 $110$ 一起输出：

110 160

其中 $160$ 对应的就是「保留 $[80,15,80]$，把重要度为 $15$ 的那块折损」。

样例 2

$N=5$、$B=12$：

块	0	1	2	3	4
重要度 $S$	8	16	24	32	40
内存 $M$	5	6	7	4	3

第一问：

右端点 $r$	窗口	内存和	重要度和	说明
0	$[0,0]$	5	8	合法
1	$[0,1]$	11	24	合法
2	$[2,2]$	7	24	加入块 2 后内存 $18$ 超预算，左端点连续右移两次
3	$[2,3]$	11	56	合法，最优 56
4	$[3,4]$	7	72	合法，最优 72

第一问答案是 $72$。

第二问：

右端点 $r$	窗口	内存和	折损对象	有效内存	折损后重要度
0	$[0,0]$	5	块 0（$S=8$，$M=5$）	$5-3=2$	$8-8=0$
1	$[0,1]$	11	块 0（$S=8$）	$11-3=8$	$24-8=16$
2	$[1,2]$	13	块 1（$S=16$，$M=6$）	$13-3=10$	$40-16=24$
3	$[2,3]$	11	块 2（$S=24$，$M=7$）	$11-4=7$	$56-24=32$
4	$[2,4]$	14	块 2（$S=24$）	$14-4=10\le12$	$96-24=72$

右端点 $r=2$ 时，$[0,2]$ 的有效内存是 $18-3=15>12$，左端点右移一格；$r=3$ 时同理，$[1,3]$ 的有效内存为 $17-3=14>12$，再右移一格。

第二问最大值是 $72$，与第一问相同：

72 72

这也说明“折损”并不总是带来额外收益 —— 折损会丢掉一块的全部重要度，只有省下的内存能换来更多块时才算得过账。

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
枚举所有区间	$O(N^2)$	$O(1)$	增量维护折损对象，$N=10^5$ 时约 $10^{10}$ 次操作
只解第一问的双指针	$O(N)$	$O(1)$	只用到内存和的单调性
双指针 + 单调队列（本题）	$O(N)$	$O(N)$	两问都 $O(N)$；队列与键数组各占 $O(N)$

$N=10^5$ 时，两遍扫描各约 $10^5$ 次循环，Python 中总运行时间约 $0.1$ 秒。

---

易错点总结

1. 折损节省的是 $\lceil M/2\rceil$，不是 $\lfloor M/2\rfloor$

折损后内存是 $\lfloor M_i/2\rfloor$，所以省下的是 $M_i-\lfloor M_i/2\rfloor=\lceil M_i/2\rceil$，代码里写 (M + 1) // 2。写成 M // 2 会让有效内存偏大，把本该合法的区间判成非法。

2. 平局规则是“内存最大”，不是“内存最小”

当多个块的重要度同为最小时，题目要求折损内存最大的那一块 —— 这样省下的内存最多。排序键要写成 $(S_i,\,-M_i,\,\text{下标})$，-M_i 保证内存大的键更小。

3. 折损对象由区间唯一确定

不能“想折损谁就折损谁”。如果自己挑一块内存大但重要度不是最小的块，算出来的方案题目并不允许。实现上不要另写一套选择逻辑，直接用单调队列维护“区间内键最小的元素”。

4. 有效内存的单调性依赖 $S_i,M_i$ 都为正

引理的证明用了 $M_j\ge1$、$\lceil M_o/2\rceil\ge1$。如果题目允许 $M_i=0$，加入零内存块时 $Eff$ 可能不变，双指针要改成“不严格单调”的写法；如果允许 $M_i<0$，单调性彻底失效，双指针会漏解。

5. 答案二至少等于答案一

折损是可选项。把 best_discount 初始化成 best_plain，可以避免“折损后反而更差”时输出一个偏小的值。

6. 左指针右移时要同步维护单调队列

队列里可能存着已经离开窗口的下标，只有“离开的那个正好是队首”时才需要 popleft()。同时 window_memory、window_score 都要减掉被移出的块。

7. 窗口可能被收空

如果单块折损后仍然超过预算，左指针会一路走到 $r+1$，此时单调队列为空。要先判断队列非空再计算候选值，否则会访问空的队首。

8. 输出两个整数

第一问、第二问的结果在同一行用空格分隔，不要只输出一个值。

---

扩展思考

• 允许折损 $k$ 块：上面的单调性不再成立 —— 折损第二块时，“有效内存”关于区间扩张不再单调（折损对象可能变化两次），需要用堆配合 DP，或者在窗口内维护“前 $k$ 小重要度”的结构。
• 折损后重要度减半而不是清零：价值公式变成 $\sum S-\lceil S_{target}/2\rceil$，被扣掉的部分仍然只与折损对象有关，所以“价值随扩张严格递增”依旧成立，双指针可以照用。
• 折损对象可以自由选择（不要求是最不重要的块）：这就变成在窗口内做“省内存 / 丢收益”的二维权衡，需要按 $S_i/M_i$ 之类的比率维护结构，难度陡增。
• 与“最多删掉一个元素”的子数组问题同源：都是“窗口里带一个特殊元素”，核心套路一致 —— 先证明某个量关于窗口扩张单调，再决定这个特殊元素用队列还是堆维护。

---

相关题目

• 滑动窗口
• 同场次：语义邻域可达