学步园

Poj中log必须用double

#include<iostream>
#include<cstdio>
#include<cmath>
//#define log(a) (int)log((double)a)
using namespace std;
int mx[50001][16],mn[50001][16],n,q;
void pre(){
	for(int i=1;i<=n;i++){
		int t;scanf("%d",&t);
		mx[i][0]=mn[i][0]=t;
	}
	int t=int(floor(log(double(n))/log(2.0)));
	for(int i=1;i<=t;i++)
		for(int j=n;j>0;j--){
			mx[j][i]=mx[j][i-1];
			if(j+(1<<(i-1))<=n)mx[j][i]=max(mx[j][i],mx[j+(1<<(i-1))][i-1]);
			mn[j][i]=mn[j][i-1];
			if(j+(1<<(i-1))<=n)mn[j][i]=min(mn[j][i],mn[j+(1<<(i-1))][i-1]);			
		}
}
int rmq(int a,int b){
	int Min,Max,t=int(floor(log(double(b-a+1))/log(2.0)));
	Max=max(mx[a][t],mx[b-(1<<t)+1][t]);
	Min=min(mn[a][t],mn[b-(1<<t)+1][t]);
	return Max-Min;
}
int main(){
	scanf("%d%d",&n,&q);pre();
	for(int i=1;i<=q;i++){
		int a,b;scanf("%d%d",&a,&b);
		printf("%d\n",rmq(a,b));
	}
	return 0;
}