1616: [ECUST2018新生赛]巧克力与小花梨

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:60 通过:8

题目描述

书接上文,小花梨和小信息闲着没事切了太多巧克力,于是他们决定将多切的巧克力分发给参加2018伊卡斯特程序设计竞赛的同学们。他们先统计了一份分发名单,第i位同学被分配了Ai块巧克力。
比赛现场:
“小花梨!有些同学想要多吃点巧克力!”
“小花梨!有些同学午饭吃撑了不要那么多巧克力!”
“小花梨!有些同学要组队打包巧克力带走!”
“小花梨!再拿一包中号袋子过来!这些人都要这么多个巧克力!”
“小花梨!”“您能消停点不!”…………
总而言之,现在出现了三大类问题:
1、小花梨需要修改第X位同学的巧克力数量为Y
2、小花梨需要求第L位同学到第R位同学的巧克力数量之和
3、小花梨需要求第L位同学到第R位同学的巧克力数量的众数,即出现次数最多的数字。
(如果存在多个众数,输出数字最小的那个)
由于人手实在不够,所以小花梨无奈把你从二食堂抓了回来。作为补偿,你可以在得到一份额外的霸王餐之外拿走剩下来的所有巧克力。

输入格式

输入只有一组数据。
第一行为两个整数N和Q,表示同学数和操作数
第二行为N个整数Ai,表示第i位同学的巧克力数
接下来Q行,先输入字符串s表示操作类型
"CHANGE X Y",表示修改第X位同学的巧克力数量为Y
"QUERY L R",求第L位同学到第R位同学的巧克力数量之和
"MOST L R",求第L位同学到第R位同学的巧克力数量的众数
(1≤N,Q≤10000,1≤Ai,Y≤109,1≤L≤R≤N,1≤X≤N)

输出格式

对于每一个操作"QUERY"和"MOST",输出一行ans,表示答案。

输入样例 复制

10 4
1 1 1 2 2 3 3 4 4 5
QUERY 2 3
MOST 2 4
CHANGE 3 2
MOST 2 4

输出样例 复制

2
1
2