题意:给定一组长度为n的不降序列,及q个询问[l,r]。求[l,r]中出现最多的数出现了几次。

分析:把相同的数(肯定是连续的)分组,记录每组有几个数、结尾的数字是原数组第几位、每组包括的数是什么。在同时记录下原数组的每个数对应第几组。这些工作在O(N)的时间内完成。然后通过预处理,rmq[j][i]保存从第j组开始2i组内出现最多的数是什么。rmq[j][i]=max(rmq[j][i-1],rmq[j+2i-1][i-1]);

对于每次询问[l,r]。如果l、r在同一组,max=r-l+1.如果l、r不在同一组,则最大值在一下四个数内:(r1为l所在的组,r2为r所在的组)

rmq[r1+1][log2(r2-1-r1)],

rmq[r2-p2[log2(r2-1-r1)]][log2(r2-1-r1)],

fns[r1]-l+1,

r-fns[r2-1]。

取最大值即可