$P1886\ 滑动窗口$

\(problem\)
\(RMQ\)问题

还是用线段树 =-=
（线段树好难调试啊\(QwQ\)）

这题与P1440 求m区间内的最小值 非常相似

就不仔细讲了 改两个地方就AC一题

#include <bits/stdc++.h>
using namespace std ;

inline int rd() { int x = 0 ; int f = 1 ; register char c ;
#define gc c = getchar()
    while(isspace(gc)) ;
    if(c == '-') f = -1 , gc ;
    while(x = (x<<1) + (x<<3) + (c&15) , isdigit(gc)) ;
    return x * f ;
#undef gc
}

const int inf = INT_MAX >> 1 ;
const int N = 1e6 + 10 ;

struct node {
    int l , r ;
    int Min , Max ;
#define lt k << 1
#define rt k << 1 | 1
}tree[N << 2] ;

int n , m ;
int a[N] ;

inline void build(int k,int l,int r) {
    if(l > r) return ;
    if(l == r) {
        tree[k].l = l , tree[k].r = r ;
        tree[k].Min = a[l] ;
        tree[k].Max = a[l] ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    build(lt , l , mid) ;
    build(rt , mid + 1 , r) ;
    tree[k].l = l , tree[k].r = r ;
    tree[k].Min = min(tree[lt].Min , tree[rt].Min) ;
    tree[k].Max = max(tree[lt].Max , tree[rt].Max) ;
}

inline int query(int k,int l,int r,int x,int y) {
    if(l > r) return 0 ;
    if(l >= x and r <= y) return tree[k].Min ;
    int mid = (l + r) >> 1 ;
    int sum = inf ;
    if(x <= mid) sum = min(sum , query(lt , l , mid , x , y)) ;
    if(y > mid) sum = min(sum , query(rt , mid + 1 , r , x , y)) ;
    return sum ;
}
inline int Query(int k,int l,int r,int x,int y) {
    if(l > r) return 0 ;
    if(l >= x and r <= y) return tree[k].Max ;
    int mid = (l + r) >> 1 ;
    int sum = -inf ;
    if(x <= mid) sum = max(sum , Query(lt , l , mid , x , y)) ;
    if(y > mid) sum = max(sum , Query(rt , mid + 1 , r , x , y)) ;
    return sum ;
}

signed main() {
    for(register int i=1;i<=(N<<2);i++) tree[i].Max = -inf , tree[i].Min = inf ;
    n = rd() , m = rd() ;
    for(register int i=1;i<=n;i++) a[i] = rd() ;
    build(1 , 1 , n) ;
    for(register int i=m;i<=n;i++) {
        int x = i - m + 1 , y = i ;
        printf("%d " , query(1 , 1 , n , x , y)) ;
    }
    puts("") ;
    for(register int i=m;i<=n;i++) {
        int x = i - m + 1 , y = i ;
        printf("%d " , Query(1 , 1 , n , x , y)) ;
    }
    return 0 ;
}

$P1886\ 滑动窗口$

原文：https://www.cnblogs.com/qf-breeze/p/10739096.html