题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
//nlogn的复杂度.
//RMQ算法。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5+10;
int f[N][50];
int n,m;
int main()
{
scanf("%d %d", &n,&m);
//f[i][j]数组初始化。
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
f[i][0]=x;
}
//构造f[i][j]数组。
int len=int(log(n)/log(2));
for(int j=1;j<=len;j++)
{
for(int i=1;i<=n-(1<<j)+1;i++)
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
//查询f[i][j]数组.
while (m -- )
{
int l,r;
scanf("%d %d",&l,&r);
int p=(int)(log(r-l+1)/log(2));
printf("%d\n",max(f[l][p],f[r-(1<<p)+1][p]));
}
return 0;
}```
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla