专栏首页wymRMQ——模板

RMQ——模板

 RMQ(rang minimun/maximun query,区间最佳查询)的主要思想是动态规划。

假设有序列a,其长度为n。定义dp状态dp[i][j],代表从a[i]开始,长度为2^j的区间的最值。则对于一次询问:查询[L,R]

的最值,就是max/min( dp[ L ][ k ], dp[ R-(2^k)+1 ][ k ] ),其中k是满足(2^k)≥R-L+1(区间长度)的最小值。

            初始化复杂度O(n*longn)

            查询复杂度O(1)

#include <bits/stdc++.h>
using namespace std;
const int maxn=10002;
int a[maxn];
int dp[maxn][20];
int n;
void init()
{
	
	for(int i=1;i<=n;i++)
		dp[i][0]=a[i];
	
	for(int j=1; (1<<j) <= n ;j++)
		for(int i=1; ( i+ ( 1<<j ) -1 ) <= n ;i++)//往后2^j个长度 位置为i+2^j-1 
			dp[i][j]=max(dp[i][j-1] , dp[i+(1 << (j-1) )][j-1]);
	
} 
int query(int l,int r)
{
	int k=0;
	while((1<<(k+1))<=(r-l+1))k++;
	return max(dp[l][k],dp[r-(1<<(k)) +1][k]);
}
int  main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
		init();
	int q;
	scanf("%d",&q);
	while(q--)
	{
		int l,r;
		scanf("%d %d",&l,&r);
		printf("%d\n",query(l,r));
	}
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 区间更新与点值

    用户2965768
  • 洛谷P1122最大子树和 树形结构计算子树和

     考虑如果子树的和为负,那么删掉它一定比不删掉它更优,用一个cut数组记录这个子树是否删去。注意这题不一定到根节点是最优的,所以要算一个子树更新一次。

    用户2965768
  • 哈尔滨理工大学软件与微电子学院第八届程序设计竞赛同步赛(高年级) 题解

    用户2965768
  • 插入排序

    #include<stdio.h> void InsertSort(int n,int a[]) { int j; for(int i=0;i...

    用户1624346
  • hdu1078

    @坤的
  • 用邻接链表存图 详讲

    在许多图论的题目中,我们首先要存图,之前我已经学习了用邻接矩阵存图 ,但是看许多大佬都是用邻接表存图,觉得还是学习下好!

    用户7727433
  • BZOJ2595: [Wc2008]游览计划(斯坦纳树,状压DP)

    attack
  • 752. [BJOI2006] 狼抓兔子

    ★★★   输入文件:bjrabbit.in   输出文件:bjrabbit.out 简单对比 时间限制:1 s   内存限制:162 MB Descripti...

    attack
  • POJ-1088 滑雪 (记忆化搜索,dp)

    滑雪 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 86318 ...

    ShenduCC
  • 【UVALive - 6534 】Join two kingdoms (树的直径的期望)

    给两棵树,分别有 n,m 个节点(1 ≤ N, Q ≤ 4 × 10^4),等概率连接属于不同树的两个节点,求新树的直径(最远两点的距离)的期望。

    饶文津

扫码关注云+社区

领取腾讯云代金券