题解：P13984 数列分块入门 9
JcWing
·
·
题解
本题禁止卡评测，一经发现将直接封禁。
题外话。
题目大意
给定一个长度为 n 的序列 a，要求支持查询 q 次 l\sim r 的众数。
## 题目分析
观察题目可以发现我们并不关心数值的大小，因此先进行离散化。
接着，我们考虑分块。
将序列 $a$ 分成 $\sqrt n$ 块，每块 $\sqrt n$ 个数（误差不计）。
我们需要以下两个数组：
- $f_{i,j}$ 表示前 $i$ 块中数值为 $j$ 的数的数量
- $g_{i,j}$ 表示第 $i$ 块到第 $j$ 块的众数
首先处理出 $f$ 数组，处理方式类似前缀和。时间复杂度为 $O(n\sqrt n)$，空间复杂度类似。
之后处理出 $g$ 数组，枚举 $i,j$ 两个端点的时间复杂度为 $O({\sqrt n}^2)$，即 $O(n)$，之后枚举这些块中的每个数，找出其中的众数，时间复杂度也是 $O(n)$。由于 $g_{i,j}$ 可以使用 $g_{i,j-1}$ 更新，每次只要遍历块 $j$ 中的数就可以了，时间复杂度降至 $O(n\sqrt n)$。
```cpp
// siz 为块的数量
// L[i] 表示块 i 的左端点，R[i] 表示块 i 的右端点
// qs 即 f 数组，com 即 g 数组
// 计算 f 数组
for (int i = 1; i <= siz; i++) { // 遍历每个块
// 类似前缀和
for (int j = 1; j <= 3e5 + 1; j++)
qs[i][j] = qs[i - 1][j];
for (int j = L[i]; j <= R[i]; j++)
qs[i][a[j]]++;
}
// 计算 g 数组
for (int i = 1; i <= siz; i++) { // 枚举左端点
for (int j = i; j <= siz; j++) { // 枚举右断点
// ansi 表示当前众数，ansk 表示当前众数在块 [i, j] 中出现的次数
// ansi 和 ansk 均继承 com[i][j - 1] 的答案
int ansi = com[i][j - 1], ansk = qs[j][ansi] - qs[i - 1][ansi];
for (int k = L[j]; k <= R[j]; k++) { // 遍历块 j
int val = a[k]; // 当前数
int num = qs[j][val] - qs[i - 1][val]; // 出现次数
// 如果当前数的出现次数超过 ansk，那么更新 ansk
// 当然，如果当前数的出现次数 = ansk，那么我们找更小的众数
if (num > ansk || (num == ansk && val < ansi)) {
ansk = num;
ansi = val;
}
}
com[i][j] = ansi;
}
}
```
---
处理完上面的两个数组后，开始考虑分块。
对于完整块，由于它们连在一起，所以直接使用 $g$ 数组就可以了。时间复杂度为 $O(\sqrt n)$。
对于不完整的块，那就暴力枚举这些不完整的块中的数，之后用 $f$ 数组就出其出现次数，继续找众数。时间复杂度为 $O(\sqrt n)$。
---
综上所述，时间复杂度为 $O(n\sqrt n)$，空间复杂度为 $O(n\sqrt n)$，可以通过 $n\le 3\times 10^5$ 的数据。
## 代码实现
:::info[代码]
```cpp line-numbers
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
// 18 * 10^7
const int N = 3e5 + 10;
const int SN = 400 + 10;
int n, a[N], d[N], cnt[N];
int pos[N], L[N], R[N];
int qs[SN][N], com[SN][SN];
int len, siz;
vector<int> vec;
int find(int x) {
int l = 0, r = vec.size() - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (vec[mid] < x) l = mid + 1;
if (vec[mid] > x) r = mid - 1;
if (vec[mid] == x) return mid + 1;
}
}
int query(int l, int r) {
int p = pos[l], q = pos[r];
if (p == q) {
// 如果左端点与右端点属于同一个块，直接暴力
int ansi = 0, ans = 0;
for (int i = l; i <= r; i++) cnt[a[i]]++;
for (int i = l; i <= r; i++) {
if (ans < cnt[a[i]]) ans = cnt[a[i]], ansi = a[i];
else if (ans == cnt[a[i]] && ansi > a[i]) ansi = a[i];
}
for (int i = l; i <= r; i++) cnt[a[i]] = 0;
return d[ansi];
}
else {
// 不然按照上述思路即可
int ansi = com[p + 1][q - 1], ans = qs[q - 1][ansi] - qs[p][ansi];
for (int i = l; i <= R[p]; i++) cnt[a[i]]++;
for (int i = L[q]; i <= r; i++) cnt[a[i]]++;
ans += cnt[ansi];
for (int i = l; i <= R[p]; i++) {
int val = cnt[a[i]] + qs[q - 1][a[i]] - qs[p][a[i]];
if (ans < val) ans = val, ansi = a[i];
else if (ans == val && ansi > a[i]) ansi = a[i];
}
for (int i = L[q]; i <= r; i++) {
int val = cnt[a[i]] + qs[q - 1][a[i]] - qs[p][a[i]];
if (ans < val) ans = val, ansi = a[i];
else if (ans == val && ansi > a[i]) ansi = a[i];
}
for (int i = l; i <= R[p]; i++) cnt[a[i]] = 0;
for (int i = L[q]; i <= r; i++) cnt[a[i]] = 0;
return d[ansi];
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i], vec.push_back(a[i]);
siz = sqrt(n * 1.0);
len = n / siz;
for (int i = 1; i <= siz; i++) {
L[i] = (i - 1) * len + 1;
R[i] = i * len;
}
// 离散化
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
for (int i = 0; i < vec.size(); i++) d[i + 1] = vec[i];
for (int i = 1; i <= n; i++) a[i] = find(a[i]);
if (R[siz] < n) siz++, L[siz] = R[siz - 1] + 1, R[siz] = n;
// 处理 f 数组
for (int i = 1; i <= siz; i++) {
for (int j = 1; j <= 3e5 + 1; j++)
qs[i][j] = qs[i - 1][j];
for (int j = L[i]; j <= R[i]; j++) {
qs[i][a[j]]++;
pos[j] = i;
}
}
// 处理 g 数组
for (int i = 1; i <= siz; i++) {
for (int j = i; j <= siz; j++) {
int ansi = com[i][j - 1], ansk = qs[j][ansi] - qs[i - 1][ansi];
for (int k = L[j]; k <= R[j]; k++) {
int val = a[k];
int num = qs[j][val] - qs[i - 1][val];
if (num > ansk || (num == ansk && val < ansi)) {
ansk = num;
ansi = val;
}
}
com[i][j] = ansi;
}
}
int m = n;
while (m--) {
int l, r;
cin >> l >> r;
cout << query(l, r) << endl;
}
return 0;
}
```
:::