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

_Manstein_ · 2025-02-14 12:30:49 · 算法·理论

这道题本来是用单调队列做的，但我看到标签里有线段树我就想尝试用线段树做

其实只需要把模板的merge函数条件改一下就行了题目太水了

#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)/