低熵体 @ 2019-03-13 00:28:36
#include <cstdio>
#include <cctype>
const int INF = 2147483647;
int getint()
{
register int x = 0;
register char ch = 0;
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 0x30), ch = getchar();
return x;
}
struct Segtree {
int t[2000005 << 2], ls[2000005 << 2], rs[2000005 << 2];
inline int lson(int p) {
return p << 1;
}
inline int rson(int p) {
return p << 1 | 1;
}
inline int min(int a, int b) {
return a < b ? a : b;
}
void build(int l, int r, int p) {
if (l == r) {
t[p] = getint();
return;
}
int mid = (l + r) >> 1;
ls[p] = lson(p), rs[p] = rson(p);
build(l, mid, ls[p]);
build(mid + 1, r, rs[p]);
t[p] = min(t[ls[p]], t[rs[p]]);
}
int query(int l, int r, int nl, int nr, int p) {
if (l <= nl && r >= nr) return t[p];
int mid = (nl + nr) >> 1;
int ans = INF;
if (l <= mid) ans = min(ans, query(l, r, nl, mid, ls[p]));
if (r > mid) ans = min(ans, query(l, r, mid + 1, nr, rs[p]));
return ans;
}
} segtree;
int main()
{
int n, m;
n = getint(); m = getint();
segtree.build(1, n, 1);
printf("0\n");
for (register int i = 1; i <= m - 1; i++)
printf("%d\n", segtree.query(1, i, 1, n, 1));
for (register int i = m + 1; i <= n; i++)
printf("%d\n", segtree.query(i - m, i - 1, 1, n, 1));
return 0;
}
by 樱初音斗橡皮 @ 2019-03-13 06:49:25
@低熵体 n这么大当然过不去,要ST表
by ニヒル @ 2019-03-13 07:18:04
@低熵体 @樱初音斗橡皮 两百万不是线性算法吗(单调队列什么的
by Mirach @ 2019-03-13 07:34:09
可以排序后用链表串串,
by RiverFun @ 2019-03-13 08:39:58
@樱初音斗橡皮 ST表过不去,会MLE
by 樱初音斗橡皮 @ 2019-03-13 22:51:44
@ニヒル @Steve_braveman 才发现这题单调队列就可以。。。
by blackfrog @ 2019-04-18 22:48:16
@樱初音斗橡皮 我咋过不了单调队列
by 樱初音斗橡皮 @ 2019-04-19 06:46:22
@blackfrog 肯定是你打错了