Một lời giải cho bài SUBSEQ - Min - Max - Length

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7, maxn = 1e6 + 5;
int bpow(int x, int y) {
    int res = 1;
    for (; y; y >>= 1) {
        if (y & 1)
            res = (1ll * res * x) % mod;
        x = (1ll * x * x) % mod;
    }
    return res;
}
ll star[maxn];
struct SegTree {
    ll lazy[4 * maxn], val[4 * maxn];
    ll tree_n;
    void resetK(ll node, ll l, ll r) {
        if (l == r) {
            lazy[node] = 1;
            val[node] = star[l];
        } else {
            ll mid = (l + r) >> 1;
            resetK(node << 1, l, mid);
            resetK((node << 1) + 1, mid + 1, r);
            lazy[node] = 1;
            val[node] = val[node << 1] + val[(node << 1) + 1];
            val[node] %= mod;
        }
    }
    void reset(ll n) {
        resetK(1, 1, n);
        tree_n = n;
    }
    void flusha(ll node, ll l, ll r) {
        lazy[node << 1] *= lazy[node];
        lazy[(node << 1) + 1] *= lazy[node];
        lazy[node << 1] %= mod;
        lazy[(node << 1) + 1] %= mod;
        ll mid = (l + r) >> 1;
        val[node << 1] *= lazy[node];
        val[(node << 1) + 1] *= lazy[node];
        val[node << 1] %= mod;
        val[(node << 1) + 1] %= mod;
        lazy[node] = 1;
    }
    void updateK(ll node, ll l, ll r, ll tar_l, ll tar_r, ll diff) {
        if ((l > tar_r) || (r < tar_l))
            return;
        else if ((l >= tar_l) && (r <= tar_r)) {
            lazy[node] *= diff;
            val[node] *= diff;
            lazy[node] %= mod;
            val[node] %= mod;
        } else {
            flusha(node, l, r);
            ll mid = (l + r) >> 1;
            updateK(node << 1, l, mid, tar_l, tar_r, diff);
            updateK((node << 1) + 1, mid + 1, r, tar_l, tar_r, diff);
            val[node] = val[node << 1] + val[(node << 1) + 1];
            val[node] %= mod;
        }
    }
    void update(ll l, ll r, ll diff) {
        if (l > r)
            return;
        updateK(1, 1, tree_n, l, r, diff);
    }
    ll getK(ll node, ll l, ll r, ll tar_l, ll tar_r) {
        if ((l > tar_r) || (r < tar_l))
            return 0;
        else if ((l >= tar_l) && (r <= tar_r)) {
            return val[node];
        } else {
            flusha(node, l, r);
            ll mid = (l + r) >> 1;
            ll cost1 = getK(node << 1, l, mid, tar_l, tar_r);
            ll cost2 = getK((node << 1) + 1, mid + 1, r, tar_l, tar_r);
            return (cost1 + cost2) % mod;
        }
    }
    ll get(ll l, ll r) {
        if (l > r)
            return 0;
        return getK(1, 1, tree_n, l, r);
    }
};
SegTree st, st1, st2;
// st.reset(n) khoi tao segtree bang gia tri trong mang star[]
// st.get(l,r) lay tong cua doan [l,r]
// st.update(l,r,x) nhan doan [l,r] voi x
ll n, m, res;
ll a[maxn], sum[maxn];
vector<ll> mins, maxs;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum[i] = a[i] + sum[i - 1];
    }
    for (int i = 1; i <= n; ++i) {
        star[i] = 1;
    }
    st.reset(n);
    for (int i = 1; i <= n; ++i) {
        star[i] = i;
    }
    st1.reset(n);
    for (int i = 1; i <= n; ++i) {
        star[i] = sum[i] % mod;
    }
    st2.reset(n);
    mins = { n + 1 }, maxs = { n + 1 };
    for (int i = n - 1; i >= 0; --i) {
        while ((mins.size() > 1) && (a[mins.back()] >= a[i + 1])) {
            ll u = bpow(a[mins.back()], mod - 2);
            st.update(mins.back(), mins[mins.size() - 2] - 1, u);
            st1.update(mins.back(), mins[mins.size() - 2] - 1, u);
            st2.update(mins.back(), mins[mins.size() - 2] - 1, u);
            mins.pop_back();
        }
        st.update(i + 1, mins.back() - 1, a[i + 1]);
        st1.update(i + 1, mins.back() - 1, a[i + 1]);
        st2.update(i + 1, mins.back() - 1, a[i + 1]);
        mins.push_back(i + 1);
        while ((maxs.size() > 1) && (a[maxs.back()] <= a[i + 1])) {
            ll u = bpow(a[maxs.back()], mod - 2);
            st.update(maxs.back(), maxs[maxs.size() - 2] - 1, u);
            st1.update(maxs.back(), maxs[maxs.size() - 2] - 1, u);
            st2.update(maxs.back(), maxs[maxs.size() - 2] - 1, u);
            maxs.pop_back();
        }
        st.update(i + 1, maxs.back() - 1, a[i + 1]);
        st1.update(i + 1, maxs.back() - 1, a[i + 1]);
        st2.update(i + 1, maxs.back() - 1, a[i + 1]);
        maxs.push_back(i + 1);
        ll u = upper_bound(sum, sum + n + 1, sum[i] + m) - sum;
        res += (st2.get(i + 1, u - 1) - (st.get(i + 1, u - 1) * (sum[i] % mod)) % mod + mod) % mod;
        res += (st1.get(u, n) - (st.get(u, n) * (i)) % mod + mod) % mod;
        res %= mod;
    }
    cout << res;
    return 0;
}