下载掌阅APP，畅读海量书库
立即打开
题目描述（POJ3368）： 给定 n 个整数的非递减序列 a 1 , a 2 , …, a n ，对每个索引 i 和 j 组成的查询（1≤ i ≤ j ≤ n ），都确定整数 a i , …, a j 中的最频繁值（出现次数最多的值）。
输入： 包含多个测试用例。每个测试用例都以两个整数 n 和 q （1≤ n ， q ≤100000）的行开始。下一行包含 n 个整数 a 1 , …, a n （-100000≤ a i ≤100000， i ∈{1, …, n }）。对每个 i ∈{1, …, n -1}，都满足 a i ≤ a i +1 。以下 q 行，每行都包含一个查询，由两个整数 i 和 j 组成（1≤ i ≤ j ≤ n ），表示查询的边界索引。在最后一个测试用例后跟一个包含单个0的行。
输出： 对每个查询，都单行输出一个整数，表示给定范围内最频繁值的出现次数。
题解： 由于本题可以将元素的出现次数累计，然后进行区间最值查询，所以可以使用ST解决。为提高求log的效率，首先用动态规划求出数据范围内所有数的log值，将其存储在数组lb[]中，使用时查询即可。F[ i ][ j ]表示[ i , i +2 j -1]区间的最大值，区间长度为2 j 。
（1）求出数据范围内所有数的log值，将其存储在数组lb[]中。
（2）非递减序列的相等元素一定相邻，将每个元素都和前面的元素比较，将重复次数累计并存入F[ i ][0]中。
（3）创建ST。
（4）查询[ l , r ]区间的最大值。若第 l 个数和前一个数相等，则首先统计第 l 个数在查询区间[ l , r ]的出现次数，再查询剩余区间的最大值，两者再求最大值即可。
（1）求出数据范围内所有数的log值，将其存储在数组lb[]中，规律如下。
· 2 i 和它的前一个数&运算必然是0，此时其log值比前一个数增加1。例如8的二进制为1000，7的二进制为111，两者与运算为0，log(8)比log(7)增加1。
· 除2 i 外，其他数和前一个数的与运算均不为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 ]区间的出现次数，再查询剩余区间的最值，比较两者的最大值。
