用块状数组求解区间众数问题

上期回顾：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) 的出现次数：

vector<unordered_map<int, int>> 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 <= R[k]; i++) {         r[a[i]]++;     } } 

这样一来，统计时我们可以前缀和相减，快速查询某个数的次数，再加上不完整块的次数即可。

(2) 块区间众数 mode
mode[i][j] 存储块 (i) 到块 (j) 的众数（离散化值）：

vector<vector<int>> mode(T, vector<int>(T, 0)); for (int i = 0; i < T; i++) {     unordered_map<int, int> cnt;     int cur_mode = 0; // 当前众数     for (int j = i; j < T; j++) {         for (int pos = L[j]; pos <= R[j]; pos++) {             cnt[a[pos]]++;             if (!cur_mode || cnt[a[pos]] > cnt[cur_mode] ||                  (cnt[a[pos]] == cnt[cur_mode] && a[pos] < cur_mode)) {                 cur_mode = a[pos];             }         }         mode[i][j] = cur_mode;     } } 

查询处理

查询区间 ([l, r]) 的众数：

1. 相邻块：暴力统计。

2. 跨块查询：

   • 中间完整块 ([p+1, q-1]) 的众数（通过 mode 获取）和零散点（左右边界）的所有数构成候选集。
   • 对候选集中的每个元素，计算其在完整块中的出现次数（通过 cnt_block 差分），加上零散部分出现次数（统计一次），比较得众数。

while (m--) {     int l, r; cin >> 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 <= 1) { // 相邻块，暴力统计         unordered_map<int, int> cnt;         int res = 0;         for (int i = l; i <= r; i++) {             cnt[a[i]]++;             if (cnt[a[i]] > cnt[res] || (cnt[a[i]] == cnt[res] && a[i] < res)) {                 res = a[i];             }         }         cout << (lastans = res) << "n";         continue;     }      // 跨块查询     vector<int> cand;     cand.push_back(mode[p + 1][q - 1]);     unordered_map<int, int> tmp_cnt;     // 处理零散点     for (int i = l; i <= R[p]; i++) {         tmp_cnt[a[i]]++;         cand.push_back(a[i]);     }     for (int i = L[q]; i <= r; i++) {         tmp_cnt[a[i]]++;         cand.push_back(a[i]);     }     // 去重     sort(cand.begin(), cand.end());     cand.erase(unique(cand.begin(), cand.end()), cand.end());      int best = 0, max_cnt = 0;     for (int x : cand) {         int total = tmp_cnt[x] + cnt[q-1][x] - cnt[p][x];         if (total > max_cnt || (total == max_cnt && x < best)) {             max_cnt = total;             best = x;         }     }     cout << (lastans = best) << "n"; } 

离散化

参考题目：https://www.luogu.com.cn/problem/P4168。但是这道题是由于元素值范围大，要先将序列离散化至 ([1, t])（(t leq n)），将哈希表改为数组才能通过：

vector<int> val = a; sort(val.begin(), val.end()); val.erase(unique(val.begin(), val.end()), val.end()); for (int i = 0; i < n; i++) {     a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin() + 1; } 

复杂度分析

• 预处理：频率处理 (O(n))，分块众数 (O(T^2 B) = O(n sqrt{n}))。
• 查询：(O(sqrt{n}))

本文题核心在于分块与预处理平衡。分块可以让预处理的规模降维。将序列划分为若干块，将问题分解为“块内”和“块间”两部分处理，将全局复杂问题转化为了局部简单问题。

而我们还在分块问题里引入了预处理，预处理的东西由思考问题性质得到，由于预处理的数组规模和块数相关，其大小也不会很大。这样需要一些思维量，但降低查询时开销。

这一思想可推广至其他无区间可加性或需动态维护统计量的问题，例如：

1. 区间数值出现次数问题：如查询区间内某值的出现次数、大于某阈值的元素个数。
2. 区间最小绝对差：维护块内有序结构，结合二分查找。
3. 其他非线性统计量：需要自己构造巧思，维护合适的东西来降低复杂度。

拓展思考：支持单点修改的区间众数问题

假如在原有问题基础上增加单点修改操作：给定位置 pos 和值 x，将 a[pos] 修改为 x。应该怎么办呢？此时，预处理失效。这个思考题困难要得多。