TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P5512
  • 問題
  • P5512历史研究
    制限 : 時間制限 : 20000 MS   メモリ制限 : 565536 KB
    審判説明 : 40组,不设单组时限
    問題説明

    IOI国历史研究的第一人——JOI教授,最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活,开始着手调查日记中记载的事件。
    日记中记录了连续N天发生的时间,大约每天发生一件。
    事件有种类之分。第i天(1<=i<=N)发生的事件的种类用一个整数Xi表示,Xi越大,事件的规模就越大。
    JOI教授决定用如下的方法分析这些日记:

    1. 选择日记中连续的一些天作为分析的时间段
    2. 事件种类t的重要度为t*(这段时间内重要度为t的事件数)
    3. 计算出所有事件种类的重要度,输出其中的最大值
      现在你被要求制作一个帮助教授分析的程序,每次给出分析的区间,你需要输出重要度的最大值。
    入力形式

    第一行两个空格分隔的整数N和Q,表示日记一共记录了N天,询问有Q次。
    接下来一行N个空格分隔的整数X1...XN,Xi表示第i天发生的事件的种类
    接下来Q行,第i行(1<=i<=Q)有两个空格分隔整数Ai和Bi,表示第i次询问的区间为[Ai,Bi]。

    出力形式

    输出Q行,第i行(1<=i<=Q)一个整数,表示第i次询问的最大重要度

    サンプル入力

    5 5
    9 8 7 8 9
    1 2
    3 4
    4 4
    1 4
    2 4

    サンプル出力

    9
    8
    8
    16
    16

    ヒント

    $1<=N<=10^5$

    $1<=Q<=10^5$

    $1<=Xi<=10^9 (1<=i<=N)$


    ソース  bzoj4241