zjbti1110 – 求m区间内的最小值(单调队列优化DP)

题目链接：zjbti1110

【题意】一个含有n项的数列(1<=n<=2000000)，求出每一项前的m个数到它这个区间内(本身不算)的最小值。若前面的数不足m项则从第1个数开始，若前面没有数则输出0。

【分析】这道题目，我们很容易想到线段树、或者st 算法之类的 RMQ 问题的解法。但庞大的数据范围让这些对数级的算法没有生存的空间。我们先尝试用动态规划的方法。用f[i]代表第i个数对应的答案，a[i]表示第i个数，很容易写出状态转移方 程：

这个方程，直接求解的复杂度是 O(nm)的，甚至比线段树还差。这时候，单调队列就发挥了他的作用：

我们维护这样一个队列：队列中的每个元素有两个域{position,value}，分别
代表他在原队列中的位置和a[i]，我们随时保持这个队列中的元素两个域都单调递增。
那计算f[i]的时候，只要在队首不断删除，直到队首的 position 大于等于
i-m+1，那此时队首的 value 必定是f[i]的不二人选，因为队列是单调的！
我们看看怎样将a[i]插入到队列中供别人决策：首先，要保证 position 单调 递增，由于我们动态规划的过程总是由小到大（反之亦然），所以肯定在队尾插入。又因为要保证队列的 value 单调递增，所以将队尾元素不断删除，直到队尾元素小于a[i]。
【时间效率分析】 很明显的一点，由于每个元素最多出队一次、进队一次，所以时间复杂度是O(n)。用单调队列完美的解决了这一题。

【AC CODE】1060ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 2000000+10;
struct NODE{
    int id,val;
    NODE(int a = 0, int b = 0){
        id = a, val = b;
    }
};
deque<NODE> q;
int a[MAXN];

int main()
{
#ifdef SHY
    freopen("e:\\1.txt", "r", stdin);
#endif
    int t;
    scanf("%d%*c", &t);
    while(t--)
    {
        int n,m;
        scanf("%d %d%*c", &n, &m);
        rep(i,0,n) scanf("%d%*c", &a[i]);
        q.clear();
        puts("0");
        rep(i,0,n-1)
        {
            //队尾加入a[i],删除>=a[i]的数
            if(q.empty()) q.push_back(NODE(i,a[i]));
            else
            {
                while(!q.empty() && a[i] < q[q.size()-1].val) q.pop_back();
                q.push_back(NODE(i,a[i]));
            }
            //更新dp[i]为队首id>i-m的值
            while(q[0].id < i-m+1) q.pop_front();
            printf("%d\n", q[0].val);
        }
    }
    return 0;
}