//本文首发于简书：https://www.jianshu.com/p/d5847d795eec
题目链接：https://vjudge.net/contest/389106#problem/D
D - 区间中最大的数（课堂练习）
给出一个有N个数的序列，编号0 - N - 1。进行Q次查询，查询编号i至j的所有数中，最大的数是多少。
例如: 1 7 6 3 1。i = 1, j = 3，对应的数为7 6 3，最大的数为7。（该问题也被称为RMQ问题）
Input
第1行：1个数N，表示序列的长度。(2 <= N <= 10000) 第2 - N + 1行：每行1个数，对应序列中的元素。(0 <= Si <= 10^9) 第N + 2行：1个数Q，表示查询的数量。(2 <= Q <= 10000) 第N + 3 - N + Q + 2行：每行2个数，对应查询的起始编号i和结束编号j。(0 <= i <= j <= N - 1)
Output
共Q行，对应每一个查询区间的最大值。
Sample Input
5
1
7
6
3
1
3
0 1
1 3
3 4
Sample Output
7
7
3
题目解析&错误示范
这道题很显然，是一道rmq问题，因为题目已经声明了……
这就是一个很模板类的题目，但是小编仍然错了好多次，那么就讲一讲rmq具体怎么理解吧。
对于rmq问题来说一般对于空间和时间都有一定要求，空间上开不起10000*10000的二维数组，时间上也总会超时。
#include<cstdio>
using namespace std;
int n,num[10000],q,x,y;
int head=0,tail=0;
int rmq[5000][5000];
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&num[i]);
for(int i=0;i<n;i++)
for(int j=i;j<n;j++)
{
if(i==j) rmq[i][j]=num[i];
else rmq[i][j]=num[j]>rmq[i][j-1]? num[j]:rmq[i][j-1];
}
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d%d",&x,&y);
printf("%d
",rmq[x][y]);
}
return 0;
}
这是小编最开始暴力求解的代码，时间复杂度为O(n^2)。
为了节约时间不得不采用O(n log n)的做法，那就是采用分治的思想。
设数组rmq[i][j]表示从i开始（包括i）后面2^j个数中的最大值，这样递推的关系式就变成了：
- 当j!=0时，rmq[i][j]=max(rmq[i][j-1],rmq[i+2^(j-1)][j-1]) （分成区间[i,2(j-1)]和[2(j-1)+1,2^j]）
- 当j==0时,rmq[i][j]=num[i] （因为这时区间内只有1个数）
查询就困难了，关系式：
max(rmq[l][k],rmq[r-(1<<k)+1][k])
但是查询更难理解，不过画个图就ok了：
为什么这个关系式设置成这样呢？假如区间长度为8（或其他2的次方数），那么就会恰好发现这样两区间就是[1,4]和[5,8]，2的k次恰好就是区间长度的一半，再加一就是下一段的起始位置，加入这个区间长度不是2的整数次，那么只能多，不能少，即使是如图的长度为6，那么也当作8来算，只不过有重叠，但是查询依然是O(1)。
错误示范：
#include<bits/stdc++.h>
using namespace std;
unsigned long long n,num[10000],q,l,r;
unsigned logg[10000],rmq[10000][50];
int main()
{
cin>>n;
logg[1]=0;
for(int i=2;i<=10000;i++)
logg[i]=logg[i/2]+1;
for(int i=0;i<n;i++)
cin>>num[i];
for(int i=0;i<n;i++)
for(int j=0;j<=logg[n];j++)
{
if(j==0) rmq[i][j]=max(num[i],num[i+1]);
else rmq[i][j]=max(rmq[i][j-1],rmq[i+(unsigned long long)(1<<(j-1)) ][j-1]);
}
cin>>q;
for(int i=1;i<=q;i++)
{
cin>>l>>r;
int k=logg[r-l+1];
cout<<max(rmq[l][k],rmq[r-(unsigned long long)(1<<k)+1][k])<<endl;
}
return 0;
}
这属于我没有弄清楚，我原理解成了i+1开始的2^k次个数，然而不是这样的：
AC代码
#include<bits/stdc++.h>
using namespace std;
int n,num[10000],q,l,r;
int logg[10000],rmq[10000][50];
int main()
{
cin>>n;
logg[1]=0;
for(int i=2;i<=10000;i++)
logg[i]=logg[i/2]+1;
for(int i=0;i<n;i++)
{
cin>>num[i];
rmq[i][0]=num[i];
}
for(int j=1;j<=18;j++)
for(int i=0;i+(1<<j)-1<=n;i++)
rmq[i][j]=max(rmq[i][j-1],rmq[i+ (1<<(j-1)) ][j-1]);
cin>>q;
for(int i=1;i<=q;i++)
{
cin>>l>>r;
int k=logg[r-l+1];
cout<<max(rmq[l][k],rmq[r-(1<<k)+1][k])<<endl;
}
return 0;
}
PS：
- for(int i=0;i+(1<<j)-1<=n;i++)这一行中判断部分不能写成i<n，虽然不清楚为什么，但是这样遇到特定数据时控制台直接罢工了……
若大佬知晓，望打在评论区内。 - pow貌似不能放进数组的[]中，会报错，所以小编这里替换成了位运算
- logg其实是因为已经有函数log了，当然直接用log函数应该也可以，记得要上取整，但是不知道为什么就RE了，还是手写吧……