A12 ST表 RMQ问题

A12 ST表 RMQ问题

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
int f[N][20];//f[x][i]表示   a[x - 2^i +1] ~~~ a[x]  的最大值
int g[N][20];//g[x][i]表示   a[x - 2^i +1] ~~~ a[x]  的最小值
template<typename T>void qr(T& x)
{
	x=0;int f=1;char c=getchar();
	for( ;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for( ; isdigit(c);c=getchar())x=x*10+c-48;
	x=x*f;
}
template<typename T>void qw(T x)
{
	if(x<0)x=-x,putchar('-');
	if(x/10)qw(x/10);
	putchar(x%10+48); 
}	

int main()
{
	int n,m,l,r,k;qr(n),qr(m);
	for(int i=1;i<=n;i++)
	{
		qr(f[i][0]);g[i][0]=f[i][0];
		for(int j=1; (1<<j)<=i;j++)
			f[i][j]=max(f[i][j-1],f[i-(1<<j-1)][j-1]),
			g[i][j]=min(g[i][j-1],g[i-(1<<j-1)][j-1]); 
	}
	while(m--)
	{
		scanf("%d%d",&l,&r);
		k=log2(r-l+1);
		printf("%d\n",max(f[l+(1<<k)-1][k],f[r][k])-min(g[l+(1<<k)-1][k],g[r][k]));
	}
	return 0;
}