问一下

P1886 滑动窗口 /【模板】单调队列

ko_no_lzx_da @ 2022-07-16 10:36:20

线段树可以过吗

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
int n,k,a[10000010];
struct node{
    int maxx;
    int minn;
}tree[1000010];
void build(int l,int r,int n){
    if(l==r){
        tree[n].maxx=tree[n].minn=a[(l+r)/2];
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,n*2);
    build(mid+1,r,n*2+1);
    tree[n].maxx=max(tree[n*2].maxx,tree[n*2+1].maxx);
    tree[n].minn=min(tree[n*2].minn,tree[n*2+1].minn); 
}
int fmin(int l,int r,int n,int L,int R){
    cout <<'-';
    if(L<=l&&r<=R){
        return tree[n].minn;
    }
    int mid=(l+r)/2;
    return min(fmin(l,mid,n*2,L,R),fmin(mid+1,r,n*2+1,L,R));
}
int fmax(int l,int r,int n,int L,int R){

    if(L<=l&&r<=R){
        return tree[n].maxx;
    }
    int mid=(l+r)/2;
    return max(fmax(l,mid,n*2,L,R),fmax(mid+1,r,n*2+1,L,R));
}
int main(){
    cin >>n>>k;
    for(int i=1;i<=n;i++){
        cin >>a[i];
    }
    build(1,n,1);
    cout <<'-';
    for(int i=1;i<=n-k;i++){
        cout<<fmin(1,n,1,i,i+k-1)<<endl<<fmax(1,n,1,i,i+k-1); 
    }
    return 0;
}

by 1lgorithm @ 2022-07-16 10:37:01

可以,但是估计要卡常


by MSqwq @ 2022-07-16 10:40:07

显然可以做,毕竟标签都有线段树


by char_cha_ch @ 2022-07-16 10:46:19

@ko_no_lzx_da 输出有问题吧


by ko_no_lzx_da @ 2022-07-16 10:55:39

@kirihara233 可以指出来吗


by 1lgorithm @ 2022-07-16 10:56:40

@ko_no_lzx_da 最小值最大值分别写循环输出吧


by ko_no_lzx_da @ 2022-07-16 11:02:41

@1lgorithm 感谢!!!Orz %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


|