模板 ST表

ST表

询问静态最值。

code：

#include <iostream>

#include <cstdio>

using namespace std;

inline int read(){

	int sum=0,f=1; char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}

	return sum*f;

}

const int wx=100017;

int f[wx][21],lo[wx];

int n,m;

void pre(){

	lo[1]=0; lo[2]=1;

	for(int i=3;i<=n;i++)lo[i]=lo[i/2]+1;

}

int query(int l,int r){

	int mid=lo[r-l+1];

	return max(f[l][mid],f[r-(1<<mid)+1][mid]);

}

int main(){

	n=read(); m=read(); pre();

	for(int i=1;i<=n;i++)f[i][0]=read();

	for(int j=1;j<=21;j++){

		for(int i=1;i+(1<<j)-1<=n;i++){

			f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);

		}

	}

	for(int i=1;i<=m;i++){

		int l,r;

		l=read(); r=read();

		printf("%d\n",query(l,r));

	}

	return 0;

}

巴特西

模板 ST表

ST表

最新文章

热门文章