問題一覧 > 通常問題

No.878 Range High-Element Query

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 137
作問者 : beetbeet / テスター : tubuanntubuann
7 ProblemId : 3287 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-09-06 20:57:11

問題文

要素数 N の順列 A={a1,a2,...,aN}  が与えられます。

以下の 1 種類のクエリが合計 Q 個与えられるので、それらを順番に処理してください。

  • 1 l r
    • Al 番目から r 番目の要素からなる数列を A[l:r] とする
    • A[l:r] に含まれる高い要素の個数を出力する
    • ここで、ある数列の i 番目の項が高いとは、その項が数列の 1 番目から i 番目の項の中で最大であることを意味する

入力

N Q
a1 a2  aN
query1
query2

queryQ

1 行目に数列の長さを表す整数 N とクエリの数を表す整数 Q がこの順で半角スペース区切りで与えられます。

2 行目には N 個の整数が半角スペース区切りで与えられ、その内の i 番目 (1iN) の整数は、初期の ai の値を表します。

続く Q 行のうちの i 行目 (1iQ) には、i 番目のクエリが与えられます。

各クエリは

  • 1 l r

のいずれかの形式で与えられます。


入力は全部で Q+2 行となり、以下の制約を満たします。

  • 入力は全て整数
  • 1N,Q105
  • 1aiN  (1iN)
  • aiaj  (ij)
  • クエリ1
    • 1lrN

出力

各クエリ1に対して、A[l:r] に含まれる高い要素の個数を改行区切りで出力してください。

サンプル

サンプル1
入力
5 5
5 1 2 4 3
1 1 5
1 1 1
1 2 4
1 2 5
1 3 5
出力
1
1
3
3
2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。