P1886[滑动窗口]线段树做法

#include <iostream>
#include <cmath>
#include <cstdio>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>//头文件
using namespace std;
const int N = 1e6 + 10;
struct node {
	long long min;//记录最大最小值（其实这里不用结构体）
}seg[N << 2];
int n, q;
int a[N];
int kt = 0;
node merge(const node& l, const node& r) {
	node res;
	if (l.min < r.min) {
		res = { l.min };
	}
	else if (l.min > r.min) {
		res = { r.min };
	}
	else {
		res = { l.min };
	}
	return res;
}//合并1最小值
node mergeX(const node& l, const node& r) {
	node res;
	if (l.min > r.min) {
		res = { l.min };
	}
	else if (l.min < r.min) {
		res = { r.min };
	}
	else {
		res = { l.min };
	}
	return res;
}//合并2最大值
void update(int id) {
	if (kt == 0)
		seg[id] = merge(seg[id << 1], seg[id << 1 | 1]);
	else
		seg[id] = mergeX(seg[id << 1], seg[id << 1 | 1]);
}
void build(int id, int l, int r) {
	if (l == r) {
		seg[id] = { a[l] };
		return;
	}
	int mid = l + r >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
	update(id);
}
node query(int id, int l, int r, int ql, int qr) {
	if (ql == l && qr == r) {
		return seg[id];
	}
	int mid = l + r >> 1;
	if (qr <= mid) {
		return query(id << 1, l, mid, ql, qr);
	}
	else if (ql > mid) {
		return query(id << 1 | 1, mid + 1, r, ql, qr);
	}
	else {
		if (kt == 0)
			return merge(query(id << 1, l, mid, ql, mid), query(id << 1 | 1, mid + 1, r, mid + 1, qr));
		else
			return mergeX(query(id << 1, l, mid, ql, mid), query(id << 1 | 1, mid + 1, r, mid + 1, qr));
	}
}
int minm[1000005];
int maxm[1000005];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int x, d;
	build(1, 1, n);
	for (int i = 1; i <= n - q + 1; i++) {
		x = i;
		d = i + q - 1;
		minm[i] = query(1, 1, n, x, d).min;
	}
	for (int i = 1; i <= 500000; i++) {
		seg[i].min = 0;
	}
	kt++;//标记
	build(1, 1, n);
	for (int i = 1; i <= n - q + 1; i++) {
		x = i;
		d = i + q - 1;
		maxm[i] = query(1, 1, n, x, d).min;//
	}
	for (int i = 1; i <= n - q + 1; i++) {
		cout << minm[i] << " ";
	}
	cout << '\n';
	for (int i = 1; i <= n - q + 1; i++) {
		cout << maxm[i] << " ";
	}
	return 0;
}//线段树代码太长了\(T-T)/