「POI 2015」WIL-Wilcze doły

假设选中区间 $[l, r]$，经过题目中的操作，获得的和为该区间的得分，其中最小的成为最小得分 $f_{l,r}$

显然得选满 $d$ 长度

所以对于区间 $[l, r]$ 只需要知道其中长度为 $d$ 的最大子段和就可以知道区间的最小得分

当然是用线段树维护啦

学数据结构果然会变傻

发现可以用单调队列维护最大子段和

然后发现若是区间 $f_{l, r} > p$ 则必然有 $\forall~x<l,y>r~~~f_{x, y} > p$

然后就是一道 two-pointer 的题了

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::make_pair;
using std::pair;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int, ll> pii;

const int N = 2000010;

ll a[N], s[N];

std::deque<pii> q;

int main() {
#ifdef LOCAL
    freopen("input", "r", stdin);
#endif
    std::ios::sync_with_stdio(false);
    cout.tie(0);
    int n, d;
    ll p;
    cin >> n >> p >> d;
    rep(i, 1, n) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    int ans = d, l = 1, r = d;
    ll c = 0;
    q.push_back(pii(1, s[d]));
    for (; r <= n; ++r) {
        // c += a[r];
        c = s[r] - s[r - d];
        while (q.size() && q.back().second <= c) q.pop_back();
        q.push_back(pii(r - d + 1, c));
        c = s[r] - s[l - 1] - q.front().second;
        while (c > p) {
            ++l;
            while (q.size() && q.front().first < l) q.pop_front();
            c = s[r] - s[l - 1] - q.front().second;
        }
        ans = std::max(r - l + 1, ans);
        // for(q.size() && q.front().first)
    }
    cout << ans;
    return 0;
}