题目描述
blablabla
样例
blablabla
算法1
线段树
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int w[N];
int n, m;
struct Node {
int l, r;
int mx = -1e9;
int mn = 1e9;
} tr[N * 4];
void pushup(int u) {
tr[u].mx = max(tr[u << 1].mx, tr[u << 1 | 1].mx);
tr[u].mn = min(tr[u << 1].mn, tr[u << 1 | 1].mn);
}
void build(int u, int l, int r) {
if (l == r)
tr[u] = {l, r, w[r], w[r]};
else {
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
int querymin(int u, int l, int r) {
if (l <= tr[u].l && r >= tr[u].r) {
return tr[u].mn;
}
int mid = tr[u].l + tr[u].r >> 1;
int sum = 1e9;
if (l <= mid)
sum = querymin(u << 1, l, r);
if (r > mid)
sum = min(sum, querymin(u << 1 | 1, l, r));
return sum;
}
int querymax(int u, int l, int r) {
if (l <= tr[u].l && r >= tr[u].r) {
return tr[u].mx;
}
int mid = tr[u].l + tr[u].r >> 1;
int sum = -1e9;
if (l <= mid)
sum = querymax(u << 1, l, r);
if (r > mid)
sum = max(sum, querymax(u << 1 | 1, l, r));
return sum;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
scanf("%d", &w[i]);
build(1, 1, n);
for (int i = 1; i <= n - m+1; i++) {
cout << querymin(1, i, i + m - 1) << " ";
}
cout << endl;
for (int i = 1; i <= n - m + 1; i++) {
cout << querymax(1, i, i + m - 1) << " ";
}
cout << endl;
return 0;
}