凑_友希那 @ 2018-04-18 22:25:34
#include <bits/stdc++.h>
using namespace std;
/**
* Code by mTx
* 题解: 砂糖表
* time: 2018/4/18
*/
///int st[22][2000001];
///short lg[2000001];
int main() {
int n, m;
scanf("%d%d", &n, &m);
int tmp = ceil(log(n) / log(2));
int **st = new int*[tmp + 1];
for(int i = 0; i <= tmp; i++) {
st[i] = new int[n + 1];
}
short *lg = new short[n + 1];
lg[0] = lg[1] = 0;
for(int i = 2; i <= n; i++) {
lg[i] = lg[i >> 1] + 1;
}
for(int i = 1; i <= n; i++)
scanf("%d", &st[0][i]);
for(int k = 0; k < tmp; k++)
for(int i = 1; i <= n; i++)
st[k + 1][i] = min(st[k][i], st[k][min(n, i + (1 << k))]);
printf("0\n");
for(int j = 1, i = 1; j < n; j++, i =max(1, j - m + 1)) {
int t = int(lg[j - i + 1]);
printf("%d\n", min(st[t][i], st[t][j - (1 << t) + 1]));
}
return 0;
}
by moongazer @ 2018-04-19 06:45:49
emmmmmmmmmmm,你可以试试单调队列
用ST表当然不行
by moongazer @ 2018-04-19 06:56:25
其实应该优化一下空间也可以
by moongazer @ 2018-04-19 06:56:51
题解中也有用ST表的