the Maxnumber (对rmq问题的初步了解)

前几天做了学弟出的一道dp，我用了简单的dp结果超时，后来学弟和我说这是一种特殊的dp方法叫rmq，所以在此膜拜一下学弟，受教了

先上百度给的解释

RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。

所以总的来说，主要就是预处理和输出这两大部分

初始化 部分

比如有一组数据 3 2 4 5 6 8 1 2 9 7

我们先将 3 2 4 5 6 8 1 2 9 7存到二维数组每行的开头

然后我们将A两个相隔1的框中值选出最大的放入B中

让后我们将B两个相距2的框中值选出最大的放入C中 （大家可以发现c1里存的其实是a1-a4 中最大值，c2其实a2-a5中的最大值......）

最后让我们将C两个相距4的框中选出最大的放入D中（大家可以发现d1里存的其实是a1-a8 中最大值，c2其实a2-a9中的最大值......）

这时由于8*2=16>10所以结束

这是对找出最大值的初始化，最小值的话只要每次找最小即可

void RMQ(int num) //预处理->O(nlogn) { for(int j = 1; j < 20; ++j) for(int i = 1; i <= num; ++i) if(i + (1 << j) - 1 <= num) { maxsum[i][j] = max(maxsum[i][j - 1], maxsum[i + (1 << (j - 1))][j - 1]); minsum[i][j] = min(minsum[i][j - 1], minsum[i + (1 << (j - 1))][j - 1]); } }

输出 部分

输出其实就是找其公共部分

比如 5-7  7-5＋1=3<4

所以只要在b列找第5（a5-a6）个和第6（a6-a7）个取最大即可 

比如 5-9  9-5+1=5<8

所以只要在c列找第5（a5-a8）个和第6（a6-a9）个取最大即可

比如 1-9 9-1+1=9>8

所以只要在d列找第1（a1-a8）个和第2（a2-a9）个取最大即可

下面就是学弟出的题在zwu.hustoj.com上的题目（1562）

问题 A: The Maxnumber

时间限制: 2 Sec   内存限制: 128 MB 提交: 26   解决: 4 [ 提交][ 状态][ 讨论版]

题目描述

新加坡的中秋节很热闹。这个节日到了一个月前，月饼就开始上市了。月饼，不仅满足了人们对吃东西的好东西吃也为祖先崇拜的节日，是亲戚朋友相互馈赠的节日优质商品。 除了月饼，中秋节的另一种节日高质量产品是“柚”。说到青年人，使他们感到兴趣的是各种制作精美的灯笼，他们也都在利用假期的机会，暴露出制作灯笼的才华，成年人也可以在 每年一度的元宵制作大赛和装饰灯笼的娱乐圈中尽情娱乐。新加坡人也可以参加由民众接触或会所举办中秋晚会。全家人都喜欢看月亮也是一种很好的行为，表现出水果和西瓜，在家 里的月饼，又加了孩子们的灯笼，是温馨、和谐的。为了使中秋佳节的气氛更浓，庆祝活动更普遍，我们建议挂上灯笼在公共场所，同时主办猜灯谜等活动。接下来我们将会给出多个 大小为N的序列，再给出M个区间，求区间中的最大值。

输入

本题包含多组数据输入到文件结束为止。首先第一行输入一个N（1<=N<=10000）,一个M（1<=M<=10000000）,第二行输入大小为N的序列（下标从0到N-1） 之后有M行，每行有两个正整数l与r（0<=l<=r<N)表示在区间[l,r]中数列的最大值.

输出

每行输出区间[l,r]中的最大值。

样例输入

2 3 14715 27442 0 0 0 1 1 1 9 2 4270 32454 13765 24867 12651 16158 31059 17400 20142 5 8 7 7

样例输出

14715 27442 27442 31059 17400

提示

可以认为序列中的数字都不超过int范围

[ 提交][ 状态]

// // main.cpp // rmq // // Created by 5201-mac on 17/7/10. // Copyright © 2017年 5201-mac. All rights reserved. // #include <iostream> #include <cstdio> #include <algorithm> int a[10000]; int rmq[10000][100]; using namespace std; int main() { int n,m; while (scanf("%d%d",&n,&m)!=EOF) { for (int i=0; i<n; i++) { scanf("%d",&a[i]); } for (int i=0; i<n; i++) { rmq[i][0]=a[i]; } for (int k=1; (1<<k)<=n; k++) { for (int l=0;l+(1<<k)-1<n; l++) { rmq[l][k]=max(rmq[l][k-1], rmq[l+(1<<(k-1))][k-1]); } } while (m--) { int l,r; scanf("%d%d",&l,&r); int len=r-l+1; int k=0; int zhan=k; for (; (1<<k)<=len; k++) { zhan=k; } printf("%d\n",max(rmq[l][zhan], rmq[r-(1<<zhan)+1][zhan])); } } // insert code here... //std::cout << "Hello, World!\n"; return 0; }