/*RMQ离线算法所谓RMQ即(Range Minimum/Maximum Query)区间最小/最大值查找，它可以用来解决多次查找区间内的最大值或最小值。算法需要O(nlogn)的初始化时间以及每次O(1)的查询时间，实在是非常的快啊。例如给定如下23个数，以数组val[23]形式给出（我随机生成的）41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36 91 4 2然后给了一大堆查询，比如查询第2个数到第5个数中的最大值。第7个数到第20个数中的最大值。核心思想是这样的，我们用一个二维数组rmq[i][j]表示从第i个数开始，长度为2^j个数的数列中最大的数，如上面这个例子中rmq[0][2] 为 41 67 34 0 中最大的数，即 67 rmq[3][0] 为 0 中最大的数，即 0 rmq[6][3] 为 78 58 62 64 5 45 81 27 中最大的数，即 78如果有了这样一个二维数组rmq，那我们查询任意一个区间[a, b]中的最大值都可以一步得出，将区间[a, b]拆成两个长度是2的幂的长度相等的区间，中间部分可以重叠。如区间 [0, 10] 拆成 [0, 7] 和 [3, 10] 转换为 rmq[0][3] 和 rmq[3][3]区间[1, 5]拆成[1, 4] 和 [2, 5] 转换为rmq[1][2] 和 rmq[2][2]区间[4, 5]拆成[4, 4] 和 [5, 5] 转换为rmq[4][0] 和 rmq[5][0] 一般的 对于区间[i,j]，令b = log(j - i + 1) 区间中的最大值为max(rmq[i][b], rmq[j - (1 << b) + 1][b]) *///这里给出查询的代码 #ifndef _RMQ_H_ #define _RMQ_H_#include <iostream> #include "algo_base.h"// 查询区间[i,j]内的最大元素 int query(int *rmq, int i, int j){int b = lb[j - i + 1];return max(rmq[i][b], rmq[j - (1<<b) + 1][b]); }其中lb数组是求一个数以2为底的对数向下取整，初始化如下#define maxn 1010 int lb[maxn];// 求最大值 inline int max(int a, int b){return a > b ? a : b; }// 初始化以二为底的对数数组 void initLb(int *lb){for(int i = 0, j = 0, k = 1, l = 1; i < maxn; i++, k--){lb[i] = j;if(k == 0){ j++; l <<= 1; k = l;}} }/* 现在的问题是rmq这个方便的东西是怎么初始化算出来的呢，我们可以用dp的方法求得，首先 rmq[i][0]就等于给出的数组val[i]转移方程为 rmq[i][j] = max( rmq[i][j -1], rmq[i + (1<<(j - 1)) ][j-1] )举个例子 rmq[2][3] 即区间 从2开始长度为8的区间，可以分成从2开始长度为4的区间和从6开始长度为4的区间。即rmq[2][2] 和 rmq[6][2].给出代码 */void init(int n){for(int i = 0; i < n; i++) rmq[i][0] = val[i];std::cout << lb[n] << endl;for(int j = 1; j <= lb[n]; j++)for(int i = 0; i < n; i++)rmq[i][j] = max(rmq[i][j -1], rmq[i + (1<<(j - 1))][j-1]); } struct Rmq {// 存储数据int* m_data;size_t m_size;Rmq(){}Rmq(int* data_, size_t size) : m_data(data_), m_size(size) {}// 创建二维数组// 递归式 rmq[i][j] = max( rmq[i][j -1], rmq[i + (1<<(j - 1)) ][j-1] )void create_2d_arr_for_query(){size_t x_cnt = m_size;size_t y_cnt =#endif