jzoj1370-飞船【RMQ初见】

2018-02-05 10:33:09来源:网络收集作者:咖啡不加糖人点击

分享

前言

RMQ就是一个在一个序列中来多次询问某段的最大值的快速的方法。其他自行度娘


正题
题目

一些成直线的星星,给出m段询问,求一段距离间最大的星星


输入输出与样例(建议无视)
输入

第一行输入N,M
接下来一行N个整数,表示星星的体积(1<=体积<=maxlongint)
接下来M行,每行两个整数L_i,R_i,表示询问区间。


输出

输出M行,每一行表示询问区间L_i到R_i之间最大星星的体积。


样例输入

6 3
5 7 3 9 2 10
1 3
2 4
3 6


样例输出

7
9
10


解题思路

就是暴力RMQ,这里讲一下RMQ。f[i][j]表示从i到i+2^j-1这个范围内的最大数。然后动态转移方程:F[i,j]=max(F[i,j-1],F[i+2^(j-1),j-1]),然后两个区间的元素个数都为2^x,所以[Li,Ri]的最大值为max(F[Li,X],F[Ri+1-2^x,X]),可以在O(E)内计算出来。


代码
#include
#include
//开log用
#include
using namespace std;
int f[100001][21],n,m,z,x,y;
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&f[i][0]);//输出
for (int j=1;(1<for (int i=1;i+(1<{
f[i][j]=max(f[i][j-1],f[i+(1< //动态转移
}
for (int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
z=(int)(log(y-x+1)/log(2));//计算x
printf("%d/n",max(f[x][z],f[y+1-(1<}
}

相关文章

    无相关信息

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台