APTX Blog

A Moe Blog Set By APTX

HDU 1806 Frequent values(区间RMQ问题)题解

洛谷:https://www.luogu.org/problemnew/show/U50167

Description

给定一个非降序的由 n 个整数构成的序列以及 q 个由整数i j 构成的询问。对于每一个询问,输出在 a[i],a[i+1], … ,a[j-1],a[j]里面出现次数最多的那个()整数出现的次数。

Input

第一行包含两个整数, n q。第二行包括 n 个整数 a[1],a[2], … ,a[n],由空格分开。以下 q 行每一行包括一个询问,一个询问由两个整数 i j 构成, i j 指示询问索引的边界。 保证 i<=j

Output

对于每一组询问,输出一行一个整数:在给定区间内出现次数最多的那个()整数出现的次数。

Sample Input

Sample Output

解析及代码

暴力:

我们考虑暴力解法,根据题意模拟即可,复杂度\(O(qn^2)\)(不计算Map复杂度)

正解①:

考虑用ST表维护区间内每个数出现的次数。对于区间l,r,我们可以分为l ->a[l]最后出现的地方 和a[r]一开始出现的地方->r 以及 a[l]最后出现的地方+1到a[r]最开始出现的地方-1三个区间。

对于第一个和第二个区间。我们暴力查找,通过二分将我们需要的a[r]一开始出现的地方 及 a[l]最后出现的地方。倘若l仍然小于r我们在查找满区间(没有被l,r分割的区间),这样我们就得到了\(O(qlogn)\)的算法。可以通过本题。

正解②:

在维护到达每一个点时每一个数的最大出现次数 时,我们可以倒序枚举,这样就不用管开头的区间了,因为保证了单调递增,这样我们RMQ查询时默认肯定会到达a[l]的最大值的。

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注