[ybtoj 高效进阶 4.3] [RMQ] 数列区间

题目

---

解题思路

这题就很像一道二分题
可用RMQ解决
f[i][j]表示以第i个数为起点，长度为2^j的区间
由f[i][j-1]和f[i+2^j-1][j-1]中取较大值
就是分为两个长度为2^j-1的区间

---

代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,a[100020],f[100020][30];
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		f[i][0]=a[i];
	}
	for (int j=1;j<=log2(n);j++)
	    for (int i=1;i+(1<<j)-1<=n;i++)
	        f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);  //状态转移
	    while (m--)
	    {
	    	  int x,y;
	    	  scanf("%d%d",&x,&y);
	    	  int t=log2(y-x+1);  //求出区间一半的长度
	    	  printf("%d\n",max(f[x][t],f[y-(1<<t)+1][t]));  
		}
	return 0;
}