Gym 100342E Minima （暴力，单调队列）

3e7暴力，800ms+过，单调队列维护区间最小值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e7+5;

int x[maxn], dq[maxn], pos[maxn];

int main()
{
    freopen("minima.in","r",stdin);
    freopen("minima.out","w",stdout);
    int n,m,k; cin>>n>>m>>k;
    ll a,b,c; cin>>a>>b>>c;
    for(int i = 1; i <= k; i++) scanf("%d",x+i);
    for(int i = k+1; i <= n; i++){
        ll t = a*x[i-2]+b*x[i-1]+c;
        x[i] = t;
    }
    int l = 0,r = 0;
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        while(r>l && dq[r-1]>=x[i]) r--;
        dq[r] = x[i];
        pos[r++] = i;
        if(i-pos[l] >= m) l++;
        if(i>=m) ans+= dq[l];
    }
    printf("%I64d
",ans);
    return 0;
}