【题目描述:】
现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。
【输入格式:】
输入一共有两行,第一行为n,k。
第二行为n个数(<INT_MAX).
【输出格式:】
输出共两行,第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
输入样例#: - - 输出样例#:
- - - -
输入输出样例
【算法分析:】
线段树使用结构体同时维护区间最小值和最大值
没有修改只有建树和查询操作,更优的方法是使用st表做RMQ
板子题.
【代码:】
//滑动窗口
#include<iostream>
#include<cstdio>
using namespace std; const int MAXN = 1e6 + ; int n, k;
int a[MAXN];
struct Segment {
int maxn, minn;
}t[MAXN << ]; void Build(int o, int l, int r) {
if(l == r) t[o].maxn = t[o].minn = a[l];
else {
int mid = (l + r) >> ;
Build(o << , l , mid);
Build(o << |, mid + , r);
t[o].maxn = max(t[o << ].maxn, t[o << |].maxn);
t[o].minn = min(t[o << ].minn, t[o << |].minn);
}
}
int max_ans, min_ans;
void Query(int o, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) {
max_ans = max(max_ans, t[o].maxn);
min_ans = min(min_ans, t[o].minn);
}
else {
int mid = (l + r) >> ;
if(ql <= mid) Query(o << , l, mid, ql, qr);
if(qr > mid) Query(o << |, mid + , r, ql, qr);
}
} int ans1[MAXN], ans2[MAXN];
int main() {
scanf("%d%d", &n, &k);
for(int i = ; i <= n; ++i)
scanf("%d", &a[i]);
Build(, , n);
for(int i = ; i + k - <= n; ++i) {
max_ans = -2e9, min_ans = 2e9;
Query(, , n, i, i + k - );
ans1[i] = max_ans, ans2[i] = min_ans;
}
for(int i = ; i <= n - k + ; ++i) printf("%d ", ans2[i]);
putchar('\n');
for(int i = ; i <= n - k + ; ++i) printf("%d ", ans1[i]);
}