根号数据结构

0x01 普通分块

[2018NOIP模拟] 蒲公英

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

[2023NOIP模拟] 徽章

Kaguya 是一个还没能辟谷的女孩子。
有一天,Kaguya 来到了食堂。食堂的队伍好长好长，居然长达 \(n\) 个同学。Kaguya 学过一点信息学，所以她将队伍中的同学依次编号为 \(1 \sim n\)。其中，有 \(n\) 个区间 \([l_i,r_i]\) 引起了她的兴趣。
Kaguya 拿出了 \(m\) 个徽章，并将第 \(i (1 \le i \le m)\) 个徽章送给了第 \(x_i\) 个人。
Kaguya 不喜欢奇数。她希望知道，\([l_1,r_1] \cdots [l_n,r_n]\) 中，有多少区间 \([l,r]\) 满足：第 \(l\) 个人到第 \(r\) 个人得到的徽章数目总和是奇数。
由于 Kaguya 非常可爱，所以你需要回答她 \(q\) 次同样形式的询问。
对于所有测试数据保证:
\(1 \le n \le 5 \times 10^5,0 \le q \le n,1 \le l_i \le r_i \le n,0 \le m,1 \le x_i \le n\)。