好题，但是也是经典题。
考虑有一个显然的 dp，\(f_i\) 表示杀掉前 \(i\) 只甲虫的最小代价，那么：
\[f_i = \min\limits_{j = i - m}^{i - 1} (f_j + \max\limits_{k = j + 1}^i a_k)
\]
看到 \(\max\) 可以想到单调栈维护一段后缀相同的 \(\max\)，同时又因为 \(j\) 的下标限制，所以我们实际上要维护一个双端队列。
思考一下要维护 \(f\) 的那个 \(\min\)，就是要支持维护一个队列，在左边删数，在右边删数，修改最左端的数，在最右端加数。
考虑先计算出来队列的中点，然后如果左边或者右边删过了中点就暴力重构。均摊复杂度 \(O(n)\)。
code
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef unsigned uint;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 2500100;
const ll mod = 1000000007;
int a[maxn], pw[maxn], q[maxn], hd = 1, tl;
ll f[maxn];
struct DS {
ll l = 1, r = 0, mid = 1, pre[maxn], suf[maxn], a[maxn];
inline void build() {
if (l > r) {
return;
}
mid = (l + r) >> 1;
suf[mid + 1] = pre[mid] = 1e18;
for (int i = mid; i >= l; --i) {
suf[i] = min(suf[i + 1], a[i]);
}
for (int i = mid + 1; i <= r; ++i) {
pre[i] = min(pre[i - 1], a[i]);
}
}
inline void dell() {
++l;
if (l > mid) {
build();
}
}
inline void delr() {
--r;
if (r < mid) {
build();
}
}
inline void addr(ll x) {
a[++r] = x;
if (l == r) {
build();
} else {
pre[r] = min(pre[r - 1], x);
}
}
inline void updl(ll x) {
a[l] = x;
suf[l] = min(suf[l + 1], x);
}
inline ll query() {
return min(suf[l], pre[r]);
}
} Q;
int solve(int n, int m, int *_a) {
pw[0] = 1;
for (int i = 1; i <= n; ++i) {
a[i] = _a[i - 1];
pw[i] = 1LL * pw[i - 1] * 23 % mod;
}
ll ans = 0;
for (int i = 1; i <= n; ++i) {
while (hd <= tl && q[hd] <= i - m) {
++hd;
Q.dell();
}
while (hd <= tl && a[q[tl]] <= a[i]) {
--tl;
Q.delr();
}
q[++tl] = i;
Q.addr(f[q[tl - 1]] + a[i]);
Q.updl(f[max(0, i - m)] + a[q[hd]]);
f[i] = Q.query();
ans = (ans + f[i] % mod * pw[n - i] % mod) % mod;
}
return ans;
}