RMQ求助
  • 板块P2251 质量检测
  • 楼主Rorou
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/8/23 18:05
  • 上次更新2024/8/23 20:45:10
查看原帖
RMQ求助
797187
Rorou楼主2024/8/23 18:05
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[100005],f[25][100005];
int query(int l,int r){
	int k=log2(r-l+1)/log(2);
	return min(f[k][l],f[k][r-(1<<k)+1]);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	memset(f,LLONG_MAX,sizeof(f));
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)f[0][i]=a[i];
	for(int i=1;i<=log2(n);i++){
		for(int j=1;j<=n-(1<<(i-1))+1;j++){
			f[i][j]=min(f[i-1][j],f[i-1][j+(1<<(i-1))]);
		}
	}
	for(int i=1;i<=n-m+1;i++){
		cout<<query(i,i+m-1)<<"\n";
	}
	return 0;
}
2024/8/23 18:05
加载中...