bit_ @ 2019-11-02 01:02:48
啊又是窝窝线段树又双叒叕写挂了qwq
#include <bits/stdc++.h>
#define int long long
using namespace std;
void Build(int, int, int);
inline void PushUp(int);
int Min(int, int, int, int, int);
int Max(int, int, int, int, int);
inline int Read();
int n, m;
int scan[11451400], tree[191981000], _tree[191981000];
signed main(signed argc, char* argv[])
{
// freopen("testdata.in", "r", stdin);
// freopen("testdata.out", "w", stdout);
n = Read(), m = Read();
for(register int i = 1; i <= n; i++)
{
scan[i] = Read();
}
Build(1, n, 1);
for(register int i = 1; i <= n - m + 1; i++)
{
printf("%d ", Min(1, n, i, i + m - 1, 1));
}
putchar('\n');
for(register int i = 1; i <= n - m + 1; i++)
{
printf("%d ", Max(1, n, i, i + m - 1, 1));
}
return 0;
}
void Build(int left, int right, int root)
{
if(left == right)
{
tree[root] = _tree[root] = scan[left];
return;
}
else
{
int mid = (left + right) >> 1;
Build(left, mid, root << 1);
Build(mid + 1, right, root << 1 | 1);
PushUp(root);
}
}
inline void PushUp(int root)
{
tree[root] = min(tree[root << 1], tree[root << 1 | 1]);
_tree[root] = max(_tree[root << 1], _tree[root << 1 | 1]);
return;
}
int Min(int left, int right, int from, int to, int root)
{
if(left >= from && right <= to)
{
return tree[root];
}
else
{
int mid = (left + right) >> 1;
int ans = 0x7f7f7f7f;
if(mid >= from) ans = min(ans, Min(left, mid, from, to, root << 1));
if(mid < to) ans = min(ans, Min(mid + 1, right, from, to, root << 1 | 1));
return ans;
}
}
int Max(int left, int right, int from, int to, int root)
{
if(left >= from && right <= to)
{
return _tree[root];
}
else
{
int mid = (left + right) >> 1;
int ans = 0;
if(mid >= from) ans = max(ans, Max(left, mid, from, to, root << 1));
if(mid < to) ans = max(ans, Max(mid + 1, right, from, to, root << 1 | 1));
return ans;
}
}
inline int Read()
{
int d = 0, o = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') o = 0;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
d = (d << 1) + (d << 3) + (ch ^ 48);
ch = getchar();
}
return (o ? d : ~d + 1);
}
by bit_ @ 2019-11-02 01:03:17
WA #2, #3, #7
by MakiseVon @ 2019-11-02 02:16:04
@bit_ 大概是 Max()
里 ans
应初始化为 -inf
qwq
by HaveFun @ 2019-11-02 07:10:41
数组太大了叭
by wwlw @ 2019-11-02 07:46:54
这不是单调队列?
by Tarsal @ 2019-11-02 08:13:04
这不是单调队列?