关于求区间众数的近10条评论(全部评论)
回复 @Skylake : 这种类型的题目也许来自于神中神陈立杰（orz%%%）的文章《区间众数解题报告》，在文章中，WJMZBMR神犇提到了除了$O((n + q) \sqrt n \log n)$ 的二分查找的做法之外的优化做法，实现了 $O((n + q) \sqrt n)$ 的时间复杂度（当然这一题不强制在线，神犇的莫队解法也很优秀，对于空间的要求要更小，比如这一题我用这个方法就会超内存），文章甚至提到了带修的区间众数解法，很具参考意义，可以看一下，已上传至 Onedrive lihaoze 2022-08-24 21:16 4楼
回复 @FoolMike : 蒲公英这个题是《算法竞赛进阶指南》上的例题，从 BZOJ 搬过来的，重题只能说是个巧合叭。不过本题的做法我找了一圈没找到，应该（大概）不会重题。。的吧 yrtiop 2022-08-24 11:15 3楼
回复 @Skylake : 原题和这个题重复了数字查询 FoolMike 2022-08-24 00:33 2楼
标程已提交，没有经过他人验题，如果有误请联系我 yrtiop 2022-08-22 23:33 1楼

3740. 求区间众数

★★★ 输入文件：IntervalMode.in 输出文件：IntervalMode.out 简单对比
时间限制：2 s 内存限制：256 MiB

注：本题和 [COGS.3231]蒲公英的区别在于更大的数据规模以及不强制在线。

给定一个长为 $N$ 的序列 $a_1,a_2,\ldots,a_N$。

$M$ 次询问，每次求出 $[l,r]$ 中出现次数最多的数。如有出现次数相同的数，取数值较小者。

第一行一个整数 $N$，表示序列长度。

接下来一行 $N$ 个整数 $a_1,a_2,\ldots,a_N$。

第三行一个整数 $M$，表示询问个数。

接下来 $M$ 行，每行两个整数 $l,r$，表示询问区间。

对于每个询问，输出一个整数，表示该询问区间的众数。

2
1
2

在此键入。

对于 30% 的数据，$1\le N,M\le 10^3$。

对于 100% 的数据，$1\le N,M \le 10^5,1\le a_i \le 10^9$。