No.878 Range High-Element Query
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 136
作問者 : beet / テスター : tubuann
タグ : / 解いたユーザー数 136
作問者 : beet / テスター : tubuann
問題文最終更新日: 2019-09-06 20:57:11
問題文
要素数 $N$ の順列 $A = \{ a_1, a_2, ... , a_N \} \ $ が与えられます。
以下の 1 種類のクエリが合計 $Q$ 個与えられるので、それらを順番に処理してください。
-
$1 \ l \ r$
- $A$ の $l$ 番目から $r$ 番目の要素からなる数列を $A[l:r]$ とする
- $A[l:r]$ に含まれる高い要素の個数を出力する
- ここで、ある数列の $i$ 番目の項が高いとは、その項が数列の $1$ 番目から $i$ 番目の項の中で最大であることを意味する
入力
$N \ Q$ $a_1 \ a_2 \ \cdots \ a_N$ $query_1$ $query_2$ $\cdots$ $query_Q$
1 行目に数列の長さを表す整数 $N$ とクエリの数を表す整数 $Q$ がこの順で半角スペース区切りで与えられます。
2 行目には $N$ 個の整数が半角スペース区切りで与えられ、その内の $i$ 番目 $(1 \le i \le N)$ の整数は、初期の $a_i$ の値を表します。
続く $Q$ 行のうちの $i$ 行目 $(1 \le i \le Q)$ には、$i$ 番目のクエリが与えられます。
各クエリは
$1 \ l \ r$
のいずれかの形式で与えられます。
入力は全部で $Q + 2$ 行となり、以下の制約を満たします。
- 入力は全て整数
- $1 \le N, Q \le 10^5$
- $1 \le a_i \le N \ \ (1 \le i \le N)$
- $a_i \neq a_j \ \ (i \neq j)$
-
クエリ1
- $1 \le l \le r \le N$
出力
各クエリ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もしくは右上の雲マークをクリックしてアカウントを作成してください。