思路与算法

先求每个位置以前b的最小值和以后a的最大值。仅当prefixMinB[k]>suffixMaxA[k+1]时，k后才允许切段，其余相邻位置必须合为原子块。每块记录A=max(a)、B=sum(b)。二分答案C，判能否把原子块分段、每段B和≤C且各段A最大值之和≤m。令f[i]为前i块的最小A代价，则f[i]=min(f[j]+max(A[j+1..i]))，其中S_i-S_j≤C。线段树为每个候选j保存此转移值。加入A_i时，用单调栈找到旧后缀最大值变大的连续j区间，对其区间加差值；新j=i-1的值单点置为f[i-1]+A_i。正B使合法j形成一个滑动后缀区间，在该区间查询最小值。

正确性说明

若在k后切段，任何左侧i与右侧j都在不同段，因此必要且充分条件是min(b_1..b_k)>max(a_{k+1}..a_n)。所有未通过的边界必须留在同一段，压原子块不丢合法方案；只在通过的边界切段则自动满足任意跨段点对条件。固定C后，最后一段从j+1到i的全部可能恰是B和不超C的j区间，故DP递推充要。后缀最大A的值按单调栈分组，新A只把不大于它的若干尾组整体提升；对应的区间加和新点插入保持线段树每个候选值准确，查询因此得到正确f[i]。删掉一个前缀末块不会增大最优代价，f[i]不下降，所以超过预算可提前判失败。增大C只放宽分段限制，可行性单调，二分得到最小最大段和。若m<全局max(a)则无解，否则整段必可行。

复杂度

设压缩后K≤n、总B和W。前后缀与压缩初始化O(n)。一次判定中每块入栈出栈各至多一次，每次单点置值、区间加和最小查询O(log K)，加上O(K)数组初始化，总O(K log K)。二分O(log W)次，整体O(n+K log K log W)，空间O(n+K)。W可达2×10^14，使用64位。

易错点

切点条件是严格大于，不能把相等也判可切。原子块的B可能远大于单个b，二分下界取最大原子块B。DP预算是各段max(A)之和，目标是max段sum(B)，不能交换。线段树候选对应切点j，组区间端点有一位偏移；每次判定必须清空栈和懒标记。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct SegmentTree {
    int n;
    vector<ll> mn, lazy;
    const ll INF = 4000000000000000000LL;
    SegmentTree(int n) : n(n), mn(4 * n), lazy(4 * n) {
    }
    void reset() {
        fill(mn.begin(), mn.end(), INF);
        fill(lazy.begin(), lazy.end(), 0);
    }
    void apply(int v, ll x) {
        mn[v] += x;
        lazy[v] += x;
    }
    void push(int v) {
        if (lazy[v]) {
            apply(v * 2, lazy[v]);
            apply(v * 2 + 1, lazy[v]);
            lazy[v] = 0;
        }
    }
    void setpoint(int v, int l, int r, int p, ll x) {
        if (l == r) {
            mn[v] = x;
            lazy[v] = 0;
            return;
        }
        push(v);
        int mid = (l + r) / 2;
        if (p <= mid)
            setpoint(v * 2, l, mid, p, x);
        else
            setpoint(v * 2 + 1, mid + 1, r, p, x);
        mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
    }
    void add(int v, int l, int r, int a, int b, ll x) {
        if (a <= l && r <= b) {
            apply(v, x);
            return;
        }
        push(v);
        int mid = (l + r) / 2;
        if (a <= mid)
            add(v * 2, l, mid, a, b, x);
        if (b > mid)
            add(v * 2 + 1, mid + 1, r, a, b, x);
        mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
    }
    ll get(int v, int l, int r, int a, int b) {
        if (a <= l && r <= b)
            return mn[v];
        push(v);
        int mid = (l + r) / 2;
        ll ans = INF;
        if (a <= mid)
            ans = min(ans, get(v * 2, l, mid, a, b));
        if (b > mid)
            ans = min(ans, get(v * 2 + 1, mid + 1, r, a, b));
        return ans;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll budget;
    if (!(cin >> n >> budget))
        return 0;
    vector<ll> a(n + 1), b(n + 1), suffix(n + 2);
    ll maxa = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        maxa = max(maxa, a[i]);
    }
    if (maxa > budget) {
        cout << "-1\n";
        return 0;
    }
    for (int i = n; i >= 1; i--)
        suffix[i] = max(suffix[i + 1], a[i]);
    vector<ll> A(1), B(1);
    ll prefixMin = LLONG_MAX, blockMax = 0, blockSum = 0;
    for (int i = 1; i <= n; i++) {
        prefixMin = min(prefixMin, b[i]);
        blockMax = max(blockMax, a[i]);
        blockSum += b[i];
        if (i == n || prefixMin > suffix[i + 1]) {
            A.push_back(blockMax);
            B.push_back(blockSum);
            blockMax = blockSum = 0;
        }
    }
    int k = A.size() - 1;
    vector<ll> S(k + 1);
    ll low = 0;
    for (int i = 1; i <= k; i++) {
        S[i] = S[i - 1] + B[i];
        low = max(low, B[i]);
    }
    ll high = S[k];
    if (k == 1) {
        cout << high << '\n';
        return 0;
    }
    SegmentTree tree(k);
    vector<int> stack;
    stack.reserve(k);
    auto feasible = [&](ll cap) {
        tree.reset();
        stack.clear();
        ll f = 0;
        int first = 0;
        for (int i = 1; i <= k; i++) {
            while (!stack.empty() && A[stack.back()] <= A[i]) {
                int p = stack.back();
                stack.pop_back();
                int left = stack.empty() ? 0 : stack.back();
                if (A[p] != A[i])
                    tree.add(1, 0, k - 1, left, p - 1, A[i] - A[p]);
            }
            stack.push_back(i);
            tree.setpoint(1, 0, k - 1, i - 1, f + A[i]);
            while (S[i] - S[first] > cap)
                first++;
            f = tree.get(1, 0, k - 1, first, i - 1);
            if (f > budget)
                return false;
        }
        return true;
    };
    while (low < high) {
        ll mid = low + (high - low) / 2;
        if (feasible(mid))
            high = mid;
        else
            low = mid + 1;
    }
    cout << low << '\n';
}