题目描述
一个含有 (n) 项的数列 ((n≤ 2000000))，求出每一项前的 (m) 个数到它这个区间内的最小值。若前面的数不足 (m) 项则从第 (1) 个数开始，若前面没有数则输出 (0)。
输入输出格式
输入格式：
-
第一行两个数 (n)，(m)。
-
第二行，(n) 个正整数，为所给定的数列。
输出格式：
- (n) 行，第 (i) 行的一个数 (a_i)，为所求序列中第 (i) 个数前 (m) 个数的最小值。
输入输出样例
输入样例 #1：
6 2
7 8 1 4 3 2
输出样例 #1：
0
7
7
1
1
3
数据规模
(m ≤ n ≤ 2000000)
原先看到标签 “RMQ”，就想用 RMQ（ST 表）写一写。显然不加滚动数组优化的 ST 表空间会爆炸（MLE，80）
/* P1440 求 m 区间内的最小值
* Au: GG
*/
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=2000005, logN=23;
int n, m, data[N], f[N][logN];
inline void ST() {
for (int i=1; i<=n; i++) f[i][0]=data[i];
for (int j=1; (1<<j)<=n; ++j)
for (int i=1; i+(1<<j)-1<=n; ++i)
f[i][j] = min(f[i][j-1], f[i+(1<<j-1)][j-1]);
}
inline int query(int l, int r) {
int k=0;
for (; (1<<k)<=(r-l+1); ++k); --k;
return min(f[l][k], f[r-(1<<k)+1][k]);
}
int main() {
scanf("%d%d", &n, &m);
for (int i=1; i<=n; ++i) scanf("%d", &data[i]);
ST(); printf("0
%d
", data[1]);
for (int i=3; i<=n; ++i) printf("%d
", query(max(i-m,1), i-1));
return 0;
}
于是就有了滚动数组优化的 ST 表尝试：
/* P1440 求 m 区间内的最小值
* Au: GG
*/
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=2000005;
int n, m, data[N], f[N][2], now=2;
int main() {
scanf("%d%d", &n, &m);
for (int i=1; i<=n; ++i) scanf("%d", &data[i]);
printf("0
%d
", data[1]);
for (int i=1; i<=n; i++) f[i][0]=data[i];
for (int j=1; (1<<j)<=m; ++j) {
for (int i=1; i+(1<<j)-1<=n; ++i)
f[i][j&1] = min(f[i][(j-1)&1], f[i+(1<<j-1)][(j-1)&1]);
for (; now<(1<<j+1); ++now) {
printf("%d
", min(f[max(1,now-m+1)][j&1], f[now-(1<<j)+1][j&1]));
}
}
int k=0;
for (; (1<<k)<=m; ++k); --k;
for (; now<n; ++now)
printf("%d
", min(f[max(1,now-m+1)][k&1], f[now-(1<<k)+1][k&1]));
return 0;
}
可惜出现了我现在（August 2018）还搞不清楚的错误：“wrong answer Too long on line 2000001. 得分 0” （WA，70）
正确的做法是 单调队列：我们只需要维护 对头（最小值）元素，所以其他对答案无贡献的元素可以直接删去。维护队头、队尾，保证队头元素在 ([i-m+1, i]) 范围内，队尾元素只要大于新添加的元素一律砍掉。为了保证队头元素的位置范围，队列里实际存储的是元素在源数据中的位置。（100）
/* P1440 求 m 区间内的最小值
* Au: GG
*/
#include <cstdio>
const int N=2000005;
int n, m, a[N], q[N], l, r;
int main() {
scanf("%d%d", &n, &m);
for (int i=1; i<=n; ++i) scanf("%d", &a[i]);
printf("0
");
for (int i=1; i<n; i++) {
while (i-q[l]+1>m && l<r) ++l;
while (a[q[r-1]]>=a[i] && l<r) --r;
q[r++]=i;
printf("%d
", a[q[l]]);
}
return 0;
}