天才的记忆

NC50449. 天才的记忆

描述

从前有个人名叫WandNandB，他有着天才般的记忆力，他珍藏了许多许多的宝藏。在他离世之后留给后人一个难题（专门考验记忆力的啊！），如果谁能轻松回答出这个问题，便可以继承他的宝藏。
题目是这样的：给你一大串数字（编号为1到N，大小可不一定哦！），在你看过一遍之后，它便消失在你面前，随后问题就出现了，给你M个询问，每次询问就给你两个数字A,B，要求你瞬间就说出属于A到B这段区间内的最大数。
一天，一位美丽的姐姐从天上飞过，看到这个问题，感到很有意思（主要是据说那个宝藏里面藏着一种美容水，喝了可以让这美丽的姐姐更加迷人），于是她就竭尽全力想解决这个问题。BUT，她每次都以失败告终，因为这数字的个数是在太多了！于是她请天才的你帮他解决。如果你帮她解决了这个问题，可是会得到很多甜头的哦！

输入描述

第一行一个整数N表示数字的个数，接下来一行为N个数。第三行读入一个M，表示你看完那串数后需要被提问的次数，接下来M行，每行都有两个整数A,B。

输出描述

输出共M行，每行输出一个数，表示对一个问题的回答。

示例1

输入:

6
34 1 8 123 3 2
4
1 2
1 5
3 4
2 3

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 104ms, 内存消耗: 20808K, 提交时间: 2020-01-29 15:43:52

#include <bits/stdc++.h>

using namespace std;

int a[200005],st[200005][25],n;

int main()
{
	int m;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",a+i),st[i][0] = a[i];
	for(int j=1;(1<<j)<=n;j++)
	for(int i=1;(i+(1<<j-1))<=n;i++)
	st[i][j] = max(st[i][j-1],st[i+(1<<j-1)][j-1]);
    scanf("%d",&m);
	while(m--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
        if(l<=1)l=1;
        if(r>=n)r=n;
		int k = log(r-l+1)/log(2);
	    int ans = max(st[l][k],st[r-(1<<k)+1][k]);
	    printf("%d\n",ans);
	}
}

C++(clang++ 11.0.1) 解法, 执行用时: 836ms, 内存消耗: 1348K, 提交时间: 2023-02-19 08:55:33

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int a[N];
int n,m;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	    cin>>a[i];
	cin>>m;
	while(m--){
		int l,r;
		cin>>l>>r;
		cout<<*max_element(a+l-1,a+r)<<endl;
	}
	return 0;
}