P2251 质量检测

https://www.luogu.com.cn/problem/P2251

ST表模板题

#include<iostream>
#include<cmath>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
typedef long long LL;
LL a[maxn];
LL dp[maxn][25];
inline LL read()
{
	LL x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
LL ST_query(LL l,LL r)
{
	LL k=log(r-l+1)/log(2);
	return min(dp[l][k],dp[r-(1<<k)+1][k]);
}
int main(void)
{
 // cin.tie(0);std::ios::sync_with_stdio(false);
	LL n,m;n=read();m=read();
	LL t=log(n)/log(2)+1;
	for(LL i=1;i<=n;i++) a[i]=read();
	for(LL i=1;i<=n;i++) dp[i][0]=a[i];
	for(LL j=1;j<t;j++)
	{
		for(LL i=1;i<=n-(1<<j)+1;i++)
		{
			dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
		}
	}
	for(LL i=1;i<=n-m+1;i++)
	{
		cout<<ST_query(i,m+i-1)<<endl; 
	}
return 0;
}

 

本文地址：https://blog.csdn.net/zstuyyyyccccbbbb/article/details/107191871