社区讨论

问一下

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 条回复,欢迎继续交流。

正在加载回复...