TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P6493
  • 問題
  • P6493己亥砸石
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    審判説明 : 2s,256MB
    問題説明

    龚自珍写了《己亥杂诗》,而熊孩子nodgd更喜欢“己亥砸石”。

    砸石头的前提是要搜集大量的石头。熊孩子nodgd有$n$块石头,重量分别为$a_1,a_2,\dots a_n$,都是正整数。nodgd经常检查自己手头的石头,他首先选择一段连续的范围,统计哪些重量在这个范围内出现过,然后选一个没有出现过的重量,去荒郊野外找一块这个重量的石头,然后狠狠砸出去。

    根据你多年以来观察熊孩子nodgd的经验,你非常了解nodgd选重量的规律:每次都会选择未出现过的最小或者次小重量。而且,你已经提前知道每次nodgd会选择哪个范围,那么聪明的你,肯定也能算出他可能砸出去多重的石头吧!

    入力形式

    第一行两个整数$n,m$,表示熊孩子nodgd拥有的石头数量和砸石头的次数。

    第二行$n$个整数$a_1,a_2,\dots,a_n$,表示每块石头的重量。

    接下来$m$行,每行贰个数$l,r$,表示熊孩子nodgd这一次砸石头的重量为第$l$到第$r$块石头范围内未出现过的第$k(=1,2)$大值。

    出力形式

    输出$m$行,每行两个数,表示熊孩子nodgd这次砸石头可能的重量,按递增顺序输出。

    サンプル入力

    6 6
    3 1 2 1 4 2
    1 2
    2 5
    5 6
    2 2
    1 1
    1 6

    サンプル出力

    2 4
    3 5
    1 3
    2 3
    1 2
    5 6

    ヒント

    设$A=\max(a_1,a_2,\dots,a_n)$,

    对于20%的数据,\(n,m,A\leq200\)

    对于40%的数据,\(n,m,A\leq 2000\)

    对于60%的数据,\(n,m,A\leq 2\times 10^4\)

    对于另外20%的数据,\(A\leq 50\)

    对于100%的数据,$1\leq n,m,A\leq2\times 10^5$,$1\leq l\leq r\leq n$,所有$a_i$都是正整数。


    ソース  nodgd命题