根号数据结构

0x01 普通分块

[2018NOIP模拟] 蒲公英

在乡下的小路旁种着许多蒲公英，而我们的问题正是与这些蒲公英有关。
为了简化起见，我们把所有的蒲公英看成一个长度为 \(n\) 的序列 \((a_1,a_2,...,a_n)\)，其中 \(a_i\) 为一个整数，表示第 \(i\) 棵蒲公英的种类编号。
而每次询问一个区间 \([L,R]\)，你需要回答区间里出现的次数最多的是哪种蒲公英，如果有若干种蒲公英出现次数相同，则输出种类编号最小的那个。
注意：你的算法必须是在线的。
\(100\%\) 的数据：\(n≤40000,m≤50000,a_i≤10^9\)。