同时限制最短长度以及最长长度的单调队列
LG-P1725为例
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, l, r;
int a[N], f[N], q[N];
int hh = 1, tt;
int ans;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> l >> r;
if (l > r) swap(l, r);
for (int i = 0; i <= n; i ++ ) cin >> a[i];
memset(f, -0x3f, sizeof f);
ans = f[0];
f[0] = 0;
for (int i = l; i <= n; i ++ )
{
if (hh <= tt && q[hh] < i - r) hh ++ ;
while (hh <= tt && f[q[tt]] < f[i - l]) tt -- ;
q[ ++ tt] = i - l;
f[i] = f[q[hh]] + a[i];
if (i + r > n) ans = max(ans, f[i]);
}
cout << ans;
}