noj 1085 区间最值 st.txt

来自「ACM资料大集合」· 文本 代码 · 共 67 行

//#include <iostream>
#include <stdio.h>
//#include <algorithm>
#include <math.h>
#include <stdlib.h>
//#include <time.h>
//using namespace std;

#define NMAX 10002
#define KMAX 15

//NOJ 1085 区间最值 RMQ
int haoer[15]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384};
int mm[NMAX];
int f[NMAX][KMAX];//f[i][j]第i位开始，长度为2^(j-1)的最大值


void print(int num)
{
	int i,j;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=4;j++)
			printf("%3d",f[i][j]);
		printf("\n");			
	}
}

void init(int num)
{
	int i,j;
	for(i=1;i<=num;i++)
		f[i][0]=mm[i];
	for(j=1;j<=14;j++)
	{
		for(i=1;i<=num-haoer[j]+1;i++)
		{
			if(f[i][j-1]<f[i+haoer[j-1]][j-1]) f[i][j]=f[i][j-1];
			else f[i][j]=f[i+haoer[j-1]][j-1];
		}
	}
//	print(num);
}

int cal(int a,int b)
{
	double aa;
	int k;
	k=(int)(((double)(log10((double)(b-a))))/((double)log10(2.00))+0.000001);
//	printf("k=%d\n",k);
//	printf("a=%.2f  b=%.2f  %.5f %.5f",aa,bb,(double)(log10((double)aa-(double)bb)),(double)log10(2.00));
//	system("pause");
	if(f[a][k]<f[b-haoer[k]+1][k]) return f[a][k];
	else return f[b-haoer[k]+1][k];
}

int main()
{
	int num,i,qnum,a,b;
	scanf("%d",&num);
	for(i=1;i<=num;i++) scanf("%d",&mm[i]);
	init(num);
//	system("pause");
	scanf("%d",&qnum);
	for(i=1;i<=qnum;i++)
	{