题解：P13984 数列分块入门 9
Lonelyhacker
·
·
题解
题意
给出一个长为 n 的数列，以及 n 个操作，操作仅有一种：
查询区间位于 [l,r] 的数字的众数。
## 题解
~~最烦这些区间众数问题了，又臭又恶心~~，但是终究是过了的。
仍然按照分块的常规思路，将问题划分为整块和散块（散点）。对于整块，由于没有修改，我们可以预处理出块 $i$ 分别到块 $\forall i' \in [i+1,\sqrt{n}]$（这个 $\sqrt{n}$ 是块的数量，此处意义为最后一个块的编号）的区间众数。这样我们可以 $O(1)$ 的求出整块的区间众数。至于散块（散点），照常暴力统计。
假设我们要求 $[l,r]$ 的区间众数，我们可以直接得到整块的结果。散块（散点）而言，假设区间众数的值为 $x$，我们还需要记录这个 $x$ 在 $[l,r]$ 中出现了多少次。然后暴力统计散块中的点（散点们）在 $[l,r]$ 中的出现次数。如果出现次数比 $x$ 的出现次数还多，或者一样多的情况下比 $x$ 小，那么更新答案。
算一下时间复杂度：预处理 $\sqrt{n}$ 个块，每次预处理从第 $i+1$ 个块遍历至最后一个块中的**所有点**，因此是 $O(n)$ 的，总的时间复杂度是 $O(n\sqrt{n})$ 的。至于查询，整块查询 $O(1)$，散块（散点）查询若不算里面的“查询 $x$ 在 $[l,r]$ 中的出现次数”的操作，复杂度是 $O(\sqrt{n})$ 的。
到这里就有一个很关键的步骤了：如何快速求出 $x$ 在 $[l,r]$ 的出现次数？直接计算是 $O(n)$ 的，而我们有 $n$ 次询问，$O(n^2\sqrt{n})$ 的复杂度直接就炸了。因此，这个操作我们需要在 $\log$ 以下的时间复杂度下完成。
看到 $\log$ 就想到二分。我们可以记录对于每个值 $x$ 的出现的位置，然后找到第一个 $>r$ 的位置（设为 $a$），和第一个 $\ge l$ 的位置（设为 $b$），两个下标一减就是结果了。仔细想想，第一个 $>r$ 的位置 $-1$ 就是不超过 $r$ 的前提下，下标的最大值。假设这个位置的下标为 $c$（显然 $c=a-1$），那么在这段区间的出现次数就是 $c-b+1$，将 $c=a-1$ 带入就是 $a-b$。
不会的话可以自己把玩一下数据，应该还是很好理解的罢。总复杂度 $O(n\sqrt{n}\log n)$。
## 代码
在 LOJ 上的 $n=5\times10^4$，代入算得大概是 $2\times10^8$ 级别的，可以通过。但是洛谷的 $n=3\times10^5$，带入算出来是 $3\times10^9$ 级别的，因此我们如果使用分块，必须**卡常**。如果你不加任何优化是过不了第二个子任务的。本人除了加快读，`inline`，修改块长为常数而非 $\sqrt{n}$，参考讨论区方法还加了个 `static` 才过。
上古注释仍然保留。
```cpp
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int N = 3e5+5;
namespace FastIO {
#ifndef _WIN32
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
const int S = 20;
int szb; char buf[S];
inline int read() {
int s = 1; char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar())
if (ch == '-') s = -1;
int x = 0;
for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
return s * x;
}
inline void write(long long x, char sep = '\n') {
if (x < 0) putchar('-'), x = -x;
do { buf[++szb] = x % 10 + '0', x /= 10; } while (x);
while (szb) putchar(buf[szb--]);
putchar(sep);
}
}
using namespace FastIO;
typedef long long ll;
int n, blo, bl[N], tot;
static ll v[N], lsh[N], cnt[N], dp[3005][3005];
vector <int> vec[N];
inline void suf(int x){
for (int i = 1; i <= n; i++) cnt[i] = 0;
int ans = 0, maxn = 0;
for (int i = (x-1)*blo+1; i <= n; i++){ // 从第x个块的左端点一直到右端点
cnt[v[i]]++;
if (cnt[v[i]] > maxn || (cnt[v[i]] == maxn && v[i] < ans))
maxn = cnt[v[i]], ans = v[i]; // 如果是新的区间众数 或者 数字个数相同但是更小
dp[x][bl[i]] = ans; // 从第x块到下标i所在块之间的区间众数就是 ans
}
}
inline int query(int l, int r, int x){ // 计算x在[l,r]的出现次数（注意到vec具有单调性）
return upper_bound(vec[x].begin(), vec[x].end(), r) - lower_bound(vec[x].begin(), vec[x].end(), l);
} // 第一个>r的位置减去第一个>=l的位置，差值即为次数
inline void solve(int l, int r){
int ans = dp[bl[l]+1][bl[r]-1], maxn = query(l, r, ans);
for (int i = l, t; i <= min(bl[l]*blo, r); i++){
t = query(l, r, v[i]);
if (t > maxn || (t == maxn && v[i] < ans))
maxn = t, ans = v[i];
}
if (bl[l] != bl[r])
for (int i = (bl[r]-1)*blo+1, t; i <= r; i++){
t = query(l, r, v[i]);
if (t > maxn || (t == maxn && v[i] < ans))
maxn = t, ans = v[i];
}
write(lsh[ans]);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
n = read();
blo = sqrt(n);
for (int i = 1; i <= n; i++){
v[i] = read();
lsh[i] = v[i];
bl[i] = (i-1)/blo+1;
}
sort(lsh+1, lsh+n+1);
tot = unique(lsh+1, lsh+n+1)-lsh-1;
for (int i = 1; i <= n; ++i)
v[i] = lower_bound(lsh+1, lsh+tot+1, v[i])-lsh,
vec[v[i]].emplace_back(i); // 存储每个v[i]的所有下标位置（按照顺序）
for (int i = 1; i <= bl[n]; i++) suf(i); // 预处理每个块
for (int i = 1, l, r; i <= n; i++){
l = read(), r = read();
solve(l, r);
}
return 0;
}
```
## 后日谈
最慢跑 $11.72$ 秒，最快跑 $5.47$ 秒，还是很猎奇的。