Rt求助dalao

Jia_k666 @ 2020-01-06 17:59:45

by Arron_HC @ 2020-01-06 18:40:31

@Jia_k666

先说第一行（比较好理解）

若改成

while(dq[l]<=i-k and l<=r) l++;

就会好理解一些

意思是：若窗口中的元素个数多于k个，便将队首元素弹出，懂？

by Jia_k666 @ 2020-01-06 18:41:21

@Arron_HC e...懂

by Arron_HC @ 2020-01-06 18:42:57

@Jia_k666

第二行其实也不难，

while(a[i]<a[dq[r]] and l<=r) r--;

你可以参照第一篇题解模拟一下，如果队尾元素后紧跟着一个大于它的元素，那么，它在有生之年必然当不成最大值，故跳出。

by Jia_k666 @ 2020-01-06 18:44:27

@Arron_HC 如此明白的解析。。。。小人如此一拜

by Arron_HC @ 2020-01-06 18:44:38

@江挽

by RAYMOND_7 @ 2020-01-06 20:18:40

别写单调队列，线段树好得很

#include <cstdio>
#define ll long long
int a[1000004],tree[5000005],big[4000004];int n,m;
inline int min(int i,int j){
    return i<j?i:j;
}
inline int max(int i,int j){
    if(i>j) return i;
        return j;
}
inline void build(int k,int l,int r){
    if(l==r){tree[k]=a[l];return ;}
    build(k<<1,l,l+r>>1);
    build(k<<1|1,(l+r>>1)+1,r);
    tree[k]=min(tree[k<<1],tree[k<<1|1]);
}
void buil(int k,int l,int r){
    if(l==r){big[k]=a[l];return ;}
    buil(k<<1,l,l+r>>1);
    buil(k<<1|1,(l+r>>1)+1,r);
    big[k]=max(big[k<<1],big[k<<1|1]);
}
inline int minn(int k,int l,int r,int x,int y){
    if(l>y||r<x) return 2147483647;
    if(x<=l&&r<=y){return tree[k];}
    int mid=l+r>>1;
    return min(minn(k<<1,l,mid,x,y),minn(k<<1|1,mid+1,r,x,y));
}
inline int maxn(int k,int l,int r,int x,int y){
    if(l>y||r<x) return -2147483647;
    if(x<=l&&r<=y){return big[k];}
    int mid=l+r>>1;
    return max(maxn(k<<1,l,mid,x,y),maxn(k<<1|1,mid+1,r,x,y));
}
void read(int &x){
    x=0;int k=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') k=-1;ch=getchar();}
    while(ch<='9'&&ch>='0') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    x*=k;
    return ;
}
int l,r;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){read(a[i]);}
    build(1,1,n);
    buil(1,1,n);
    for(int i=1;i<=n-m+1;++i){
        l=i;r=i+m-1;
        printf("%d ",minn(1,1,n,l,r));
    }
    printf("\n");
    for(int i=1;i<=n-m+1;++i){
        l=i;r=i+m-1;
        printf("%d ",maxn(1,1,n,l,r));
    }
    return 0;
}