题目传送门

代码：

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

int n, m;
int sum;
int a[_];

inline int read()
{
    int ans = 0, fh = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            fh = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        ans = ans * 10 + ch - '0', ch = getchar();
    return ans * fh;
}

struct Tree
{
    int z, f, h, lazy;
} tr[_ << 2];

void push_up(int o)
{
    tr[o].h = max(tr[o << 1].h, tr[o << 1 | 1].h);
    tr[o].f = min(tr[o << 1].f, tr[o << 1 | 1].f);
    tr[o].z = min(tr[o << 1].z, tr[o << 1 | 1].z);
}

void push_down(int o)
{
    if (tr[o].lazy)
    {
        tr[o << 1].h = tr[o].lazy;
        tr[o << 1].z = tr[o << 1].f + tr[o].lazy;
        tr[o << 1].lazy = tr[o].lazy;
        tr[o << 1 | 1].h = tr[o].lazy;
        tr[o << 1 | 1].z = tr[o << 1 | 1].f + tr[o].lazy;
        tr[o << 1 | 1].lazy = tr[o].lazy;
        tr[o].lazy = 0;
    }
}

inline void insert(int o, int l, int r, int d, int qf, int qh)
{
    if (l == r)
    {
        tr[o].f = qf;
        tr[o].h = qh;
        tr[o].z = qf + qh;
        return;
    }
    int mid = (l + r) >> 1;
    push_down(o);
    if (d <= mid)
        insert(o << 1, l, mid, d, qf, qh);
    else
        insert(o << 1 | 1, mid + 1, r, d, qf, qh);
    push_up(o);
}

inline void revise(int o, int l, int r, int ql, int qr, int qz)
{
    if (ql <= l && qr >= r)
    {
        tr[o].h = qz;
        tr[o].z = tr[o].f + qz;
        tr[o].lazy = qz;
        return;
    }
    int mid = (l + r) >> 1;
    push_down(o);
    if (ql <= mid)
        revise(o << 1, l, mid, ql, qr, qz);
    if (qr > mid)
        revise(o << 1 | 1, mid + 1, r, ql, qr, qz);
    push_up(o);
}

inline int geth(int o, int l, int r, int ql, int qr)
{
    if (ql <= l && qr >= r)
        return tr[o].h;
    int mid = (l + r) >> 1;
    int Ans = 0;
    push_down(o);
    if (ql <= mid)
        Ans = max(Ans, geth(o << 1, l, mid, ql, qr));
    if (qr > mid)
        Ans = max(Ans, geth(o << 1 | 1, mid + 1, r, ql, qr));
    return Ans;
}

inline int getz(int o, int l, int r, int ql, int qr)
{
    if (ql <= l && qr >= r)
        return tr[o].z;
    int mid = (l + r) >> 1;
    int Ans = INT_MAX;
    push_down(o);
    if (ql <= mid)
        Ans = min(Ans, getz(o << 1, l, mid, ql, qr));
    if (qr > mid)
        Ans = min(Ans, getz(o << 1 | 1, mid + 1, r, ql, qr));
    return Ans;
}

inline int getl(int l, int r, int z)
{
    int Ans = r + 1;
    int R = r;
    r++;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (geth(1, 1, n, mid, R) < z)
            Ans = r = mid;
        else
            l = mid + 1;
    }
    return Ans;
}

signed main()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    insert(1, 1, n, 1, 0, a[1]);
    for (int l = 1, r = 1; r <= n; r++)
    {
        sum += a[r];
        while (sum > m)
            sum -= a[l++];
        int x = getl(l, r - 1, a[r]);
        if (x < r)
            revise(1, 1, n, x, r - 1, a[r]);
        if (r == n)
            cout << getz(1, 1, n, l, r) << endl;
        else
            insert(1, 1, n, r + 1, getz(1, 1, n, l, r), a[r + 1]);
    }
    return 0;
}