思路和蓝书一致，记录一下实现细节

dp过程中有两类决策点
1. $A_j = max_{j\le k\le i}\{A_k\}$
2. $\sum_{k=j}^iA_k > M,其中j是符合条件中最小的那个$

其中第二类决策点可以用st表直接转移，或者在单调队列处理过程中顺便获得最大值
而第一类决策点需要用到两个数据结构来维护和转移就显得比较麻烦

单调队列维护的是一个决策点 j 单调递增、数值$A_j$递减的队列。其中j是最为一个决策点而存在，并且是第一类决策点。

决策点可以被多个点作为最优决策，所以在二叉堆中要用唯一的id来标识每一种转移。

考虑当前维护好的单调队列（即已经把当前元素插入到了队尾），可以发现除去队尾之外，其他队列中的元素都可以作为决策点来进行转移，并且转移费用是它在单调队列中后面的一个元素的值（唯一，并且一定有这样一个元素）。但是我们要保证这些决策点的转移都已经存在了二叉堆中，这样才能及时更新。考虑添加当前元素到队尾的操作，如果在添加之前队列中已经有元素的话，我们就可以计算由队尾元素作为决策，当前元素作为转移费用时的一个转移，并将其添加到堆中，记id为当前元素的下标（这样做不仅仅是为了方便）。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 100000 + 5;

int n, a[N], l, r, q[N], del[N], lg2[N];
ll m, sum[N], c[N], d[N], max_val[N][20];

ll ask(int l,int r){
    int t = log(r-l+1)/log(2);
    return max(max_val[l][t], max_val[r - (1 << t) + 1][t]);
}
void read_init(){
    scanf("%d%lld", &n, &m);
    for (int i = 2; i <= n;i++){
        lg2[i] = lg2[i / 2] + 1;
    }

    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        max_val[i][0] = a[i];
        sum[i] = a[i] + sum[i - 1];
        c[i] = lower_bound(sum, sum + i + 1, sum[i] - m) - sum; // 找到最小的 j 满足 sum[i] - sum[j] <= m
    }

    int t = log(n) / log(2) + 1;
    for (int j = 1;j < t; j++){
        for (int i = 1; i <= n - (1 << j) + 1;i++){
            max_val[i][j] = max(max_val[i][j - 1], max_val[i + (1 << (j - 1))][j - 1]);
        }
    }
}
int main() {
    read_init();

    l = 0, r = -1;
    priority_queue<pair<ll, int> > heap;

    for (int i = 1; i <= n;i++){
        while(l <= r && q[l] < c[i]){ // 维护单调队列单调性，删除队头
            del[q[l]] = 1;
            l++;
        }
        d[i] = d[c[i]] + ask(c[i] + 1, i); // 由 c[i] 转移

        //下面的转移，所选的决策j必须满足 a[j] = max(a[k]); j<=k<=i;
        //二叉堆中记录的下标 k, a[k] 是 j+1 到 i中的最大值，故此刻单调队列队头已经不能作为这个k，即要从二叉堆中删除

        del[q[l]] = 1;

        while(l <= r && a[q[r]] <= a[i]){ //删除队尾元素
            del[q[r]] = 1; // 此刻的q[r]也要从二叉堆中删除，因为a[i] 已经大于a[q[r]]，a[q[r]]不能作为任何决策的转移增长值
            r--;
        }

        if(l <= r){ // 如果队尾还有元素，则在堆中添加以 q[r] 为决策点，以 a[i] 为转移费用的更新值
            heap.push({ -d[q[r]] - a[i], i });
        }

        while(heap.size() && del[heap.top().second]) // 懒惰删除
            heap.pop();

        if(heap.size()) d[i] = min(d[i], -heap.top().first); // 如果堆中还有元素则更新

        q[++r] = i; // 队尾添加元素

    }
    cout << d[n] << endl;
    return 0;
}