《CF380A区间频率统计的高效解法探索》聚焦Codeforces经典区间统计问题，针对暴力查询易超时的痛点，系统剖析多种优化方案，莫队算法通过离线排序查询、分块处理区间，将时间复杂度优化至O(n√n)，适配大规模数据场景；若数值范围有限，前缀和数组可实现O(1)单次查询，简洁高效；分块法则兼顾在线查询需求，平衡预处理与查询耗时，这些解法的对比探索，不仅为该问题提供多元最优解思路，更助力开发者深化区间统计类问题的算法选型与优化思维。
在编程竞赛的竞技场中，Codeforces（简称CF）的题目往往是算法思维的试金石，编号为380A的题目，以其对区间内元素频率统计的巧妙考察，成为初学者理解离线处理与数据结构应用的经典范例，这道题看似简单，却隐藏着从暴力到高效优化的思维跃迁，能帮助我们深刻体会算法设计的核心逻辑。 详解描述 给定一个由n个整数组成的序列a，以及m个查询，每个查询包含两个整数l和r（1≤l≤r≤n），要求针对区间[l, r]输出三个结果：
- 恰好出现一次的不同整数的个数；
- 恰好出现两次的不同整数的个数；
- 至少出现三次的不同整数的个数。
数据范围
- 1 ≤ n, m ≤ 10^5
- 序列元素值范围为1 ≤ a[i] ≤ 10^5
从数据范围可以直接判断：暴力遍历每个查询区间统计频率的O(qn)解法必然超时,我们需要寻找时间复杂度更优的方案。
解题思路分析
核心问题拆解
要解决这个问题，关键在于高效统计每个查询区间内不同元素的出现次数，并分类计数，直接统计每个元素在区间内的次数成本过高，因此我们需要借助离线处理和数据结构（如树状数组）来优化计算流程。
离线处理与贡献标记
我们可以将所有查询按右边界r排序，同步遍历序列元素，动态维护各元素的出现状态，并通过树状数组记录每个位置对不同计数类别的贡献,具体步骤如下：
-
预处理元素出现位置：遍历序列，用字典存储每个元素所有出现的索引位置，例如
pos[x]是元素x出现的索引列表。 -
标记计数贡献：
- 对于元素x的第1次出现位置p1：在p1处给“恰好一次”计数数组+1；若x有第2次出现位置p2，则在p2处给“恰好一次”数组-1，同时给“恰好两次”数组+1；
- 对于元素x的第2次出现位置p2：若x有第3次出现位置p3，则在p3处给“恰好两次”数组-1；
- 对于元素x的第3次及以后出现位置pk：无需修改前两个计数数组，因为此时x已属于“至少三次”的类别。
-
统计区间不同元素个数：同样采用离线方法，遍历序列时记录每个元素最后一次出现的位置，用树状数组维护“是否为新出现元素”的标记，查询区间[l, r]的和即为该区间内不同元素的总数。
-
计算最终结果：对于每个查询[l, r]：
- ans1 = “恰好一次”数组在[l, r]的区间和；
- ans2 = “恰好两次”数组在[l, r]的区间和；
- ans3 = 区间不同元素总数 - ans1 - ans2；
代码实现示例（C++）
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
struct Query {
int l, r, idx;
};
int a[MAXN];
vector<int> pos[MAXN];
vector<Query> qs;
int ans1[MAXN], ans2[MAXN], ans3[MAXN];
// 树状数组模板
struct FenwickTree {
vector<int> tree;
int n;
FenwickTree(int size) : n(size), tree(size + 1, 0) {}
void update(int idx, int delta) {
while (idx <= n) {
tree[idx] += delta;
idx += idx & -idx;
}
}
int query(int idx) {
int res = 0;
while (idx > 0) {
res += tree[idx];
idx -= idx & -idx;
}
return res;
}
int range_query(int l, int r) {
return query(r) - query(l - 1);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
pos[a[i]].push_back(i);
}
qs.resize(m);
for (int i = 0; i < m; ++i) {
cin >> qs[i].l >> qs[i].r;
qs[i].idx = i;
}
// 按r排序查询，处理恰好一次和恰好两次的计数
sort(qs.begin(), qs.end(), [](const Query& x, const Query& y) {
return x.r < y.r;
});
FenwickTree ft1(n), ft2(n);
int ptr = 0;
for (int i = 1; i <= n; ++i) {
int x = a[i];
auto& p = pos[x];
int idx = lower_bound(p.begin(), p.end(), i) - p.begin();
if (idx == 0) {
// 第一次出现
ft1.update(i, 1);
if (p.size() >= 2) {
ft1.update(p[1], -1);
ft2.update(p[1], 1);
}
} else if (idx == 1) {
// 第二次出现
if (p.size() >= 3) {
ft2.update(p[2], -1);
}
}
// 处理当前r=i的查询
while (ptr < m && qs[ptr].r == i) {
int l = qs[ptr].l, idx = qs[ptr].idx;
ans1[idx] = ft1.range_query(l, i);
ans2[idx] = ft2.range_query(l, i);
ptr++;
}
}
// 处理区间不同元素个数
FenwickTree ft_distinct(n);
vector<int> last_occur(MAXN, 0);
ptr = 0;
sort(qs.begin(), qs.end(), [](const Query& x, const Query& y) {
return x.r < y.r;
});
for (int i = 1; i <= n; ++i) {
int x = a[i];
if (last_occur[x] != 0) {
ft_distinct.update(last_occur[x], -1);
}
ft_distinct.update(i, 1);
last_occur[x] = i;
while (ptr < m && qs[ptr].r == i) {
int l = qs[ptr].l, idx = qs[ptr].idx;
int distinct = ft_distinct.range_query(l, i);
ans3[idx] = distinct - ans1[idx] - ans2[idx];
ptr++;
}
}
// 输出结果
for (int i = 0; i < m; ++i) {
cout << ans1[i] << " " << ans2[i] << " " << ans3[i] << "\n";
}
return 0;
}
总结与思考
CF380A的核心考察点在于离线处理思想和数据结构的灵活运用，通过将查询按右边界排序，我们可以在遍历序列的过程中动态维护状态，避免重复计算，将时间复杂度从暴力的O(qn)优化到O(n logn + q logn),完美适配大数据范围。
对于初学者而言，这道题是理解“离线处理”和“区间统计”的绝佳案例，它提醒我们，在面对大规模数据时，不能局限于直观的暴力解法，而要学会从问题本质出发，寻找状态维护的规律，借助合适的数据结构降低时间复杂度，这种思维方式不仅适用于编程竞赛,也能迁移到日常开发中的性能优化场景。