P1514天才的记忆 背景 神仙飞啊飞
描述 从前有个人名叫W and N and B,他有着天才般的记忆力，他珍藏了许多许多的宝藏。在他离世之后留给后人一个难题(专门考验记忆力的啊！)，如果谁能轻松回答出这个问题，便可以继承他的宝藏。题目是这样的：给你一大串数字（编号为1到N，大小可不一定哦！），在你看过一遍之后，它便消失在你面前，随后问题就出现了，给你M个询问，每次询问就给你两个数字A,B，要求你瞬间就说出属于A到B这段区间内的最大数。一天，一位美丽的姐姐从天上飞过，看到这个问题，感到很有意思（主要是据说那个宝藏里面藏着一种美容水，喝了可以让这美丽的姐姐更加迷人），于是她就竭尽全力想解决这个问题。BUT，她每次都以失败告终，因为这数字的个数是在太多了！于是她请天才的你帮他解决。如果你帮她解决了这个问题，可是会得到很多甜头的哦！
格式 输入格式 一个整数N表示数字的个数,接下来一行为N个数。第三行读入一个M，表示你看完那串数后需要被提问的次数，接下来M行，每行都有两个整数A,B。
输出格式 输出共M行，每行输出一个数。
模板：
#include<iostream> #include<cstdio> #include<ctime> #include<cstdlib> #include<cmath> #include<cstring> #include<string> #include<set> #include<map> #include<vector> #include<queue> #include<algorithm> #ifdef WIN32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif #define CLOCK CLOCKS_PER_SEC #define cle(x) memset(x,0,sizeof(x)) #define maxcle(x) memset(x,0x3f,sizeof(x)) #define mincle(x) memset(x,-1,sizeof(x)) #define maxx(x1,x2,x3) max(x1,max(x2,x3)) #define minn(x1,x2,x3) min(x1,min(x2,x3)) #define cop(a,x) memcpy(x,a,sizeof(a)) #define FROP "hdu" #define LL long long #define smin(x,tmp) x=min(x,tmp) #define smax(x,tmp) x=max(x,tmp) using namespace std; const int N = 200010; int a[N]; int rmq[N][20],n,m; void RMQ_init() { for(int i = 1;i <= n; i++)rmq[i][0]=a[i]; for(int j = 1;(1<<j)<=n;j++) for(int i = 1;i+(1<<j)-1<=n;i++) rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]); } int RMQ(int L,int R) { int k = 0; while((1<<(k+1))<=R-L+1)k++; return max(rmq[L][k],rmq[R-(1<<k)+1][k]); } void init() { scanf("%d",&n); for(int i= 1;i <= n; i++) scanf("%d",&a[i]); scanf("%d",&m); RMQ_init(); } int main() { freopen(FROP".in","r",stdin); freopen(FROP".out","w",stdout); init(); for(int i = 1;i <= m; i++) { int x,y; scanf("%d%d",&x,&y); printf("%d\n",RMQ(x,y)); } return 0; }