训练2　最频繁值

题目描述（POJ3368）：给定n个整数的非递减序列a1, a2, …, an，对每个索引i和j组成的查询（1≤i≤j≤n），都确定整数ai, …, aj中的最频繁值（出现次数最多的值）。

输入：包含多个测试用例。每个测试用例都以两个整数n和q（1≤n，q≤100000）的行开始。下一行包含n个整数a1, …, an（-100000≤ai≤100000，i∈{1, …, n}）。对每个i∈{1, …, n-1}，都满足ai≤ai+1。以下q行，每行都包含一个查询，由两个整数i和j组成（1≤i≤j≤n），表示查询的边界索引。在最后一个测试用例后跟一个包含单个0的行。

输出：对每个查询，都单行输出一个整数，表示给定范围内最频繁值的出现次数。

题解：由于本题可以将元素的出现次数累计，然后进行区间最值查询，所以可以使用ST解决。为提高求log的效率，首先用动态规划求出数据范围内所有数的log值，将其存储在数组lb[]中，使用时查询即可。F[i][j]表示[i, i+2j-1]区间的最大值，区间长度为2j。

1. 算法设计

（1）求出数据范围内所有数的log值，将其存储在数组lb[]中。

（2）非递减序列的相等元素一定相邻，将每个元素都和前面的元素比较，将重复次数累计并存入F[i][0]中。

（3）创建ST。

（4）查询[l, r]区间的最大值。若第l个数和前一个数相等，则首先统计第l个数在查询区间[l, r]的出现次数，再查询剩余区间的最大值，两者再求最大值即可。

2. 完美图解

（1）求出数据范围内所有数的log值，将其存储在数组lb[]中，规律如下。

• 2i和它的前一个数&运算必然是0，此时其log值比前一个数增加1。例如8的二进制为1000，7的二进制为111，两者与运算为0，log(8)比log(7)增加1。

• 除2i外，其他数和前一个数的与运算均不为0，其log值与前一个数相等。

首先，log[0]=-1。

1&0=0：log[1]=log[0]+1=0。

2&1=0：log[2]=log[1]+1=1。

3&2=2：log[3]=log[2]=1。

4&3=0：log[4]=log[3]+1=2。

5&4=4：log[5]=log[4]=2。

6&5=4：log[6]=log[5]=2。

7&6=6：log[7]=log[6]=2。

8&7=0：log[8]=log[7]+1=3。

……

（2）将输入样例中元素的出现次数累计并存入F[i][0]中。

（3）创建ST。

（4）查询。2 3：查询[2, 3]区间最频繁值的出现次数。首先，t=l=2，因为a[2]=a[1]，t++，即t=3；此时a[3]≠a[2]，t-l=1，RMQ(t, r)=RMQ(3, 3)=1，求两者的最大值，得到[2, 3]区间最频繁值的出现次数为1。注意：不可以直接查询RMQ(2, 3)，想一想，为什么？

（5）查询。1 10：查询[1, 10]区间最频繁值的出现次数。首先，t=l=1，a[1]≠a[0]，t-l=0，RMQ(t, r)=RMQ(1, 10)=4，求两者的最大值，得到[1, 10]区间最频繁值的出现次数为4。

（6）查询。5 10：查询[5, 10]区间最频繁值的出现次数。首先，t=l=5，因为a[5]=a[4]，t++，即t=6；a[6]=a[5]，t++，即t=7；此时a[7]≠a[6]，t-l=2，RMQ(t, r)=RMQ(7, 10)=3，求两者的最大值，得到[5, 10]区间最频繁值的出现次数为3。

若直接查询RMQ(5, 10)=4，但是a[5]在[5, 10]区间的出现次数是2，则不是4。因此若a[l]和前一个数a[l-1]相等，则需要先统计a[l]在[l, r]区间的出现次数，再查询剩余区间的最值，比较两者的最大值。

3. 算法实现