题目背景
Alice 和 Bob 玩游戏。
题目描述
Alice 现在有一个序列 a1,a2,…an。
现在她需要 Bob 支持询问一个区间内的众数,还要支持修改一个位置的 ai 。
输入格式
第一行两个整数 n,m。
第二行 n 个整数，表示 a1,…,an。
接下来 m 行，每行三个整数 flag,x,y。
如果 flag=0，表示询问 [x,y] 区间内的众数，如果有多个输出较小的。
如果 flag=1，表示将 ax改为 y。
输出格式
对于每个 flag=0的询问，每行输出一个整数表示答案。
输入输出样例 输入 #1
5 3 1 1 2 2 1 0 1 4 1 2 3 0 1 4输出 #1
1 2说明/提示
对于 100% 的数据 n,m≤1000。
对于查询操作满足 x≤y。
任意时刻 0 < ai ≤ 10^9。
我的思路
此题是一题简单的模拟题，只需根据题目要求什么就写什么，本题的核心是求众数，所以小编用了一下桶来统计每个数出现的个数，需要注意的是ai <= 10^9, 我建议用map<int, int> 来存储。
if (b[a[i]] > Max) { Max = b[a[i]]; t = a[i]; } else if (b[a[i]] == Max && a[i] < t) { Max = b[a[i]]; t = a[i]; }至于上面这个代码为什么要分两种情况，因为小编是[x,y]这个区间一个一个统计的，第一个if是保存当前统计最多的数并记住此数。第二个if是寻找统计个数相同，数值最小。因为数值小的数可能后面出现。
AC代码
#include<bits/stdc++.h> using namespace std; int n, m, flag, x, y, a[1001]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; while (m--) { int Max = 0, t; map<int, int> b; cin >> flag >> x >> y; if (!flag) { for (int i = x; i <= y; i++) { b[a[i]]++; if (b[a[i]] > Max) { Max = b[a[i]]; t = a[i]; } else if (b[a[i]] == Max && a[i] < t) { Max = b[a[i]]; t = a[i]; } } cout << t << endl; } else a[x] = y; } return 0; }