P1997 faebdc的烦恼

    • 129通过
    • 542提交
  • 题目提供者 YuMiko_Stereo
  • 评测方式 云端评测
  • 标签 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    鸟哥(faebdc)自从虐暴NOIP2013以来依然勤奋学习,每天上各种OJ刷题,各种比赛更是不在话下。但这天他遇到了一点小小的麻烦……在一届“Orz鸟哥杯”上,题目是在是太多了!足有n道!鸟哥看得头晕眼花,他需要你的帮助。

    每道题都有一个难度值ai,由于wangxz神犇已经提前帮助鸟哥将这些难度值升序排列,所以鸟哥并不想知道哪些题难度低或者高,他只想知道在某些题目ai,ai+1,…,aj中,出现最多的难度值出现的次数(他为啥想知道这么奇葩的东西呢……自己去问)。

    你的任务就是对于鸟哥的每一次询问(i,j),告诉他在从ai到aj这j-i+1道题之中,出现最多的难度值出现的次数(询问共有q次)。

    如果你成功地帮助了鸟哥,鸟哥将会带你通过省选。

    题目描述

    给出一个升序排列的整数数组a1,a2,…an,你的任务是对于鸟哥的一系列询问(i,j),回答ai,ai+1,…aj中出现次数最多的值所出现的次数。

    输入输出格式

    输入格式:

    输入仅包含一组数据。

    第一行为两个整数n,q(1<=n<=100000,1<=q<=200000)。第二行包含n个升序排列的整数a1,a2,…,an(-100000<=ai<=100000),代表每一道题的难度值。以下q行每行包含两个整数i和j(1<=i<=j<=n),代表鸟哥询问的区间。

    输出格式:

    对于每次询问,单独输出一行,该行仅有一个整数,表示该区间内出现最多的数值所出现的次数。

    输入输出样例

    输入样例#1: 复制
    9 1
    1 1 1 2 2 3 3 4 4
    3 8
    输出样例#1: 复制
    2
    

    说明

    各个测试点1s

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。