D. 封锁元素 题解（单调队列优化版）

---

题意回顾

给定长度为 $n$ 的数组 $a$，选择一些位置封锁，设封锁位置为 $b_1 < b_2 < \dots < b_m$。代价定义为以下两者的最大值：

$$\max\left( \sum_{k=1}^m a_{b_k},\ \max_{1 \le i \le m+1} \text{sum}(segment_i) \right) $$

其中 $segment_i$ 是移除封锁元素后形成的连续段。求最小可能代价。

---

核心思路：二分答案 + 动态规划 + 单调队列

1. 二分答案的单调性

若代价 $x$ 可行，则任意 $y \ge x$ 显然也可行（保持原封锁方案即可）。因此答案关于 $x$ 单调，可以使用二分搜索。

• 下界 $l = 0$（或 $\max a_i$，但 $0$ 足够）。
• 上界 $r = \sum_{i=1}^n a_i \le 10^{14}$（最大可能代价为封锁所有元素）。
• 二分次数固定为 $60$ 次（$2^{60} > 10^{18}$），足以覆盖范围，且避免边界判断。

2. 判定函数：检查给定 $x$ 是否可行

给定候选代价 $x$，我们需要判断是否存在一种封锁方案，满足：

1. 封锁元素的总和 $\le x$；
2. 任意未封锁的连续段的和 $\le x$。

我们可以在数组末尾添加一个虚拟元素 $a_n = 0$，作为必然被封锁的终点（代价为 $0$）。这样，原问题等价于选择一组位置 $0 \le j_0 < j_1 < \dots < j_k = n$，满足：

• 对于每对相邻封锁位置 $(j_{t-1}, j_t)$，中间段的和 $\sum_{i=j_{t-1}+1}^{j_t-1} a_i \le x$；
• 所有封锁位置上的元素和（不含虚拟终点） $\le x$。

我们希望封锁元素和尽可能小，因此定义 $dp[j]$ 表示考虑位置 $j$ 被封锁时，从 $j$ 到 $n$ 这一段内封锁元素的最小总代价（包含 $a_j$，若 $j=n$ 则代价为 $0$）。

转移方程：

$$dp[j] = a_j + \min_{\substack{k > j \\ \sum_{i=j+1}^{k-1} a_i \le x}} dp[k] $$

其中 $k$ 是下一个封锁位置，要求中间段的和 $\le x$。特别地，$dp[n] = 0$。

最终，若存在某个 $j$（$0 \le j \le n$）满足：

• 从数组开头到 $j-1$ 的和 $\le x$（即第一段合法），
• 且 $dp[j] \le x$（封锁代价合法），

则 $x$ 可行。此外，完全不封锁（即整个数组和 $\le x$）的情况也需考虑。

3. 滑动窗口与单调队列优化

直接枚举 $k$ 的转移复杂度为 $O(n^2)$，无法接受。注意到条件 $\sum_{i=j+1}^{k-1} a_i \le x$ 等价于前缀和约束：

$$pre[k-1] - pre[j] \le x \quad \Longleftrightarrow \quad pre[k-1] \le pre[j] + x $$

其中 $pre[t] = \sum_{i=1}^t a_i$（设 $pre[0] = 0$）。随着 $j$ 的减小，$pre[j]$ 递减，因此满足条件的 $k$ 的范围是一个向左滑动的窗口：左端点随 $j$ 减小而向右移动。

我们采用从后向前的 DP 顺序。对于当前 $j$，维护一个窗口 $[j+1, p2]$，其中 $p2$ 是满足 $\sum_{i=j+1}^{p2-1} a_i \le x$ 的最大右端点。窗口内的所有 $k$ 均可作为下一个封锁位置。我们需要查询窗口内最小的 $dp[k]$。

由于窗口边界单调移动，且需要维护最小值，可以使用 单调队列：

• 队列中存储候选下标，并按 $dp$ 值递增排列（队首最小）。
• 当窗口右移（$p2$ 减小）时，若队首元素等于被移出的下标，则弹出队首。
• 当插入新下标 $j$ 时，从队尾弹出所有 $dp$ 值大于等于 $dp[j]$ 的元素，以保持单调性，然后将 $j$ 加入队尾。

这样，每次转移可以 $O(1)$ 获取最小值，整体判定复杂度降为 $O(n)$。

4. 算法步骤

1. 读入 $n$ 和数组 $a$，计算总和 $sum_a$。
2. 二分答案 $x$，范围 $[0, sum_a]$（或固定 $60$ 次迭代）。
3. 对每个 $x$ 进行判定：
   • 初始化 $dp[n] = 0$，清空单调队列，将 $n$ 入队。
   • 维护窗口右端点 $p2 = n$，当前窗口和 $sum = 0$。
   • 从 $j = n-1$ 递减到 $0$：
     • 将 $a[j]$ 加入 $sum$（扩展窗口）。
     • 当 $sum > x$ 时，循环右移 $p2$：$sum$ 减去 $a[p2-1]$，若队首为 $p2$ 则弹出，$p2 \gets p2 - 1$。
     • 此时队首即为窗口内最小的 $dp$ 值对应的下标，计算 $dp[j] = dp[q.front()] + a[j]$。
     • 将 $j$ 插入队列：弹出队尾所有 $dp$ 值 $\ge dp[j]$ 的元素，再将 $j$ 入队。
   • 检查可行性：计算前缀和，若存在 $j$ 满足 $\sum_{i=0}^{j-1} a_i \le x$ 且 $dp[j] \le x$，则 $x$ 可行。同时判断完全不封锁的情况。
4. 输出二分得到的最终 $l$ 值。

---

复杂度分析

• 单次判定：每个元素最多入队、出队一次，时间复杂度 $O(n)$。
• 二分次数：固定 $60$ 次或 $O(\log(\sum a_i))$。
• 总时间复杂度：$O(t \cdot 60 \cdot n)$，在 $\sum n \le 10^5$ 下约为 $6 \times 10^6$ 次操作，非常快。

---

参考代码（含详细注释）

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 2e5 + 10;

// 全局静态数组，避免动态分配
ll a[MAXN];
ll dp[MAXN];
deque<int> q;   // 单调队列，存储下标，按 dp 值递增

// 快速读入
inline ll read() {
    ll x = 0;
    char c = getchar_unlocked();
    while (c < '0' || c > '9') c = getchar_unlocked();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar_unlocked();
    return x;
}

int main() {
    int t = read();
    while (t--) {
        int n = read();
        ll sum_a = 0;
        for (int i = 0; i < n; i++) {
            a[i] = read();
            sum_a += a[i];
        }

        ll l = 0, r = sum_a;
        // 固定 60 次二分，足够覆盖 1e14 范围且无边界判断
        for (int _ = 0; _ < 60; _++) {
            ll m = (l + r) >> 1;
            q.clear();

            int p2 = n;
            dp[n] = 0;
            q.push_back(n);
            ll sum = 0;   // 窗口 [j+1, p2-1] 的元素和

            for (int j = n - 1; j >= 0; j--) {
                sum += a[j];
                // 维护窗口和 <= m，若不满足则右移 p2
                while (sum > m) {
                    sum -= a[p2 - 1];
                    // 如果队首下标刚好是被移出窗口的 p2，弹出队首
                    if (!q.empty() && q.front() == p2) q.pop_front();
                    p2--;
                }

                // 队首即为窗口内最小 dp 值对应的下标
                dp[j] = dp[q.front()] + a[j];

                // 维护单调队列：保持 dp 值递增
                while (!q.empty() && dp[q.back()] >= dp[j]) q.pop_back();
                q.push_back(j);
            }

            // 检查是否存在可行的起始封锁点
            ll s = 0;
            bool ok = false;
            for (int j = 0; j < n; j++) {
                if (s <= m && dp[j] <= m) {
                    ok = true;
                    break;
                }
                s += a[j];
            }
            // 完全不封锁的情况
            if (!ok && sum_a <= m) ok = true;

            if (ok) r = m;
            else l = m + 1;
        }
        printf("%lld\n", l);
    }
    return 0;
}

---

总结

本题综合考察了二分答案、动态规划与滑动窗口最小值维护。通过将问题转化为判定性问题，并利用单调队列在 $O(n)$ 时间内完成判定，再结合二分法，最终在 $O(n \log S)$ 的时间复杂度内求解，完美契合了数据范围的要求。代码中采用固定次数的二分与快速读入进一步提升了运行效率。