记录编号	74021	评测结果	WWWWWWWWTT
题目名称	延绵的山峰	最终得分	0
用户昵称	ranto	是否通过	未通过
代码语言	C++	运行时间	2.515 s
提交时间	2013-10-23 19:46:09	内存使用	3.28 MiB

#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

ifstream in("climb.in");
ofstream out("climb.out");

long n;
int *f;
int **fm;
//int *frontmax;
//int *backmax;

void input_preproc();
void proc();
void output();

int main()
{	
	input_preproc();
	proc();
	output();
	return 0;
}

void input_preproc()
{
	in>>n;
	f=new int [n+1];
	fm=new int *[n+1];
	//frontmax=new int [n+1];
	//backmax=new int [n+1];
	int len(static_cast<int>(log(n)/log(2)));
	for(int i=0;i!=n+1;++i)
	{
		in>>f[i];
		fm[i]=new int [len];
		fm[i][0]=f[i];
	}
	///////////////////
	//frontmax[0]=f[0];
	//backmax[n]=f[n];
	/*for(int i=1;i!=n+1;++i)
	{
		if(f[i]>frontmax[i-1])
		{
			frontmax[i]=f[i];
		}
		else 
		{
			frontmax[i]=frontmax[i-1];
		}
		if(f[n-i]>backmax[n-i+1])
		{
			backmax[n-i]=f[n-i];
		}
		else
		{
			backmax[n-i]=backmax[n-i+1];
		}
	}*/
	for(int j=1;j<=len;++j)
    {
        for(int i=0;i+(1<<j)<n+1;++i)
        {
            int m=i+(1<<(j-1));
            fm[i][j]=max(fm[i][j-1],fm[m][j-1]);
			out<<fm[i][j]<<' ';
        }
		out<<endl;
	}
	return ;
}

void test()
{
	out<<"max"<<endl;
	/*for(int i=0;i!=n+1;++i)
	{
		out<<frontmax[i]<<' ';
	}
	out<<endl<<"max"<<endl;
	for(int i=0;i!=n+1;++i)
	{
		out<<backmax[i]<<' ';
	}*/
}

inline int find(int s,int e)
{
	int len=static_cast<int>(log(static_cast<double>(e-s+1))/log(2.0));
	return max(fm[s][len],fm[e-(1<<len)+1][len]);
}

void proc()
{
	//test();
	int t;
	in>>t;
	for(int i=0;i!=t;++i)
	{
		int start,end;
		in>>start>>end;
		/*if(frontmax[start]<frontmax[end])
		{
			out<<frontmax[end]<<endl;
			continue;
		}
		if(backmax[end]<backmax[start])
		{
			out<<backmax[start]<<endl;
			continue;
		}if(start==end)
		{
			out<<f[start]<<endl;
			continue;
		}*/
		if(start==end)
		{
			out<<f[start]<<endl;
			continue;
		}
		out<<find(start,end)<<endl;
	}
	return ;
}

void output()
{
	
	return ;
}