社区讨论
问一下
P1886【模板】单调队列 / 滑动窗口参与者 4已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @lo8kgnlg
- 此快照首次捕获于
- 2023/10/27 20:05 2 年前
- 此快照最后确认于
- 2023/10/27 20:05 2 年前
线段树可以过吗
CPP#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;
}
回复
共 6 条回复,欢迎继续交流。
正在加载回复...