区间查询时统计每个数出现次数，维护出现次数最大且数值最小的那个数；修改直接单点赋值。
OJ: luogu
题目 ID: P2681
难度:入门
标签:模拟枚举
日期: 2026-06-19 01:11
题意
给定一个序列，支持两种操作：
0 x y：查询区间[x, y]的众数1 x y：把a[x]修改成y
如果区间里有多个众数，输出其中较小的那个。
思路
这题的数据范围很小：n, m <= 1000。
所以查询时没有必要上复杂数据结构，直接统计区间出现次数就够了。
先看一个更直接的朴素做法：
对区间里的每个数，再扫一遍区间，数它一共出现了几次，然后取出现次数最大、数值最小的那个。
这个版本最容易理解，也方便对拍：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n, m;
int a[MAXN];
int query_mode(int l, int r) {
int best_value = 0;
int best_count = -1;
// 枚举区间里的每一个数，重新数它出现了多少次。
for (int i = l; i <= r; i++) {
int cur_value = a[i];
int cur_count = 0;
for (int j = l; j <= r; j++) {
if (a[j] == cur_value) {
cur_count++;
}
}
if (cur_count > best_count ||
(cur_count == best_count && cur_value < best_value)) {
best_count = cur_count;
best_value = cur_value;
}
}
return best_value;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= m; i++) {
int flag, x, y;
cin >> flag >> x >> y;
if (flag == 0) {
cout << query_mode(x, y) << '\n';
}
else {
a[x] = y;
}
}
return 0;
}正式做法可以稍微省一点重复工作：
查询 [l, r] 时，从左到右扫一遍区间，用 map 统计每个数出现了多少次。
每当某个数的计数加一时，就检查它是否能更新当前答案：
- 出现次数更多，一定更优
- 出现次数相同，则数值更小更优
修改操作就直接做单点赋值。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n, m;
int a[MAXN];
int query_mode(int l, int r) {
map<int, int> cnt;
int best_value = 0;
int best_count = 0;
for (int i = l; i <= r; i++) {
cnt[a[i]]++;
if (cnt[a[i]] > best_count ||
(cnt[a[i]] == best_count && a[i] < best_value)) {
best_count = cnt[a[i]];
best_value = a[i];
}
}
return best_value;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= m; i++) {
int flag, x, y;
cin >> flag >> x >> y;
if (flag == 0) {
cout << query_mode(x, y) << '\n';
}
else {
a[x] = y;
}
}
return 0;
}复杂度
设一次查询区间长度为 len。
- 查询复杂度是
- 修改复杂度是
在本题数据范围下完全够用。
总结
这题的重点是看到数据范围很小，不要过度设计。
按题意直接统计频率，就是最稳的做法。