上期回顾：https://www.cnblogs.com/ofnoname/p/18994725
在上一篇文章中，我们介绍了块状数组的基本原理。
而区间众数问题就是一个典型的适合用分块解决的问题。由于众数不满足区间可加性，直接使用传统数据结构（如线段树）较为困难。但块状数组通过预处理块内信息，结合零散点处理，能在亚线性时间内完成查询。
问题描述
给定长度为 \(n\) 的序列 \(a\) 和 \(m\) 次查询，每次查询区间 \([l, r]\) 的众数（出现次数最多，相同取最小）。
数据范围：\(n, m \leq 4 \times 10^4\)，\(a_i \leq 10^9\)。
（强制在线，仅查询而没有修改）
分块设置
块大小 \(B = \lceil \sqrt{n} \rceil\)，块数 \(T = \lceil n / B \rceil\)。- int B = ceil(sqrt(n)), T = (n + B - 1) / B; // B: 块大小 T: 块数量
- vector<int> b(n), L(T), R(T);
- for (int i = 0; i < n; i++) b[i] = i / B;
- for (int i = 0; i < T; i++) {
- L[i] = i * B;
- R[i] = min(n - 1, (i + 1) * B - 1); // 闭区间
- }
由于众数是无法由子区间众数合并的，因此无论如何我们总需要查询一个数的区间出现次数。
预处理的内容基于这样一个事实：一个区间的众数，要么是所有中间完整块（他们一起）的众数，要么是一个出现在不完整块中的数（想想看）。
所以候选数的总数量是根号数量级，我们要快速解决单个数出现次数的查询
(1) 前缀和数组
cnt[k][x] 表示前 \(k\) 块中元素 \(x\) 的出现次数：
[code]vector cnt(T + 1);for (int k = 0; k < T; k++) { auto &r = cnt[k]; if (k) r = cnt[k - 1]; for (int i = L[k]; i > l >> r; l = (l + lastans - 1) % n; r = (r + lastans - 1) % n; if (l > r) swap(l, r); int p = b[l], q = b[r]; if (q - p |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
