众数

题目背景

Alice 和 Bob 玩游戏。

题目描述

Alice 现在有一个序列 $a_1,a_2,...a_n$。

现在她需要 Bob 支持询问一个区间内的众数,还要支持修改一个位置的 $a_i$。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数，表示 $a_1,...,a_n$。

接下来 $m$ 行，每行三个整数 $flag,x,y$。

如果 $flag=0$，表示询问 $[x,y]$ 区间内的众数，如果有多个输出较小的。

如果 $flag=1$，表示将 $a_x$ 改为 $y$。

输出格式

对于每个 $flag=0$ 的询问，每行输出一个整数表示答案。

样例 #1

样例输入 #1

5 3
1 1 2 2 1
0 1 4
1 2 3
0 1 4

样例输出 #1

1
2

提示

对于 $100\%$ 的数据 $n,m\le 1000$。

对于查询操作满足 $x\le y$。

任意时刻 $0<a_i\le 10^9$。

C++实现

#include
#include
using namespace std;
int a[2927],b[2927];
void zhongshu(int i,int j){
for (int k=i;k<=j;k++)b[k]=a[k];
sort(b+i,b+j+1);
int answer=0,tmp=1,maxx=0;
for (int k=i+1;k<=j;k++){
if (b[k]!=b[k-1]){
if (tmp>answer){
maxx=b[k-1];
answer=tmp;
}
tmp=1;
}
else tmp++;
}
if (tmp>answer){
maxx=b[j];
answer=tmp;
}
cout<<maxx<<endl;
}
int main(){
int n,m;
cin>>n>>m;
for (int i=1;i<=n;i++)cin>>a[i];
for (int i=1;i<=m;i++){
int g,h,l;
cin>>g>>h>>l;
if (g==0)zhongshu(h,l);
else a[h]=l;
}
return 0;
}

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容