学习总结

最近主要看了RMQ算法的相关题目。这两天杂事比较多，所以看得进度比较慢。幸亏下周就没什么杂事啦，可以多学很多。

RMQ问题可以解决对于一个整数数组(也可以是其他可比较大小的元素类型)的任意区间[L, R]查询最值时，能在经过O(nlogn)的时间预处理后，做到O(1)时间复杂度的任意区间最大最小值查询。接下来大概写一下几种题目：

题目：给出一个非降序排列的整数数组a1,a2,...an，你的任务是对于一系列询问(i, j)，回答ai,ai+1,...aj中出现最多次数的值所出现的次数？

思路：转化一下。把输入序列分成一段段由相同值构成的序列，然后对于每个查询[L，R]看他覆盖了哪些段，只要再这些连续的段范围内找出现次数的最大值即可，RMQ问题

题目思路：二维RMQ问题，求一个矩阵N*M中的一个小块矩阵内的最值问题.其中dmin[i][j][ii][jj]=x表示以(i , j)为左上角,以( i+(1<<ii)-1, j+(1<<jj)-1 )为右下角的矩阵内的最小值.dmax的值类似.把二维问题转变为一维问题来求解.

题目：在给定序列中求出一个区间，最小值是左边界，最大值是右边界。求最大区间长度。

思路：用RMQ存下最大值与最小值，然后枚举区间左边界，再用二分法找出满足“最小值是左边界”这个条件的最大区间的右边界编号，然后在这个区间里求出最大值，就是要求的区间了。