問題一覧 > 通常問題

No.1921 Range LthKth Query

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 7
作問者 : tatyam
3 ProblemId : 8080 / 自分の提出
問題文最終更新日: 2022-05-01 23:51:17

問題文

NN 要素の整数列 A=(A1,A2,,AN)A = (A_1, A_2, \dots, A_N) と、整数 K,LK, L が与えられます。

以下の形式のクエリが QQ 個与えられるので、それぞれについて答えを求めてください。

  • 整数 l,rl, r が与えられる。整数列 B=(Al,Al+1,,Ar)B = (A_l, A_{l + 1}, \dots, A_r)LL 番目の KK 番目の数 を求めよ。

入力

入力は以下の形式で標準入力から与えられる。

NN KK LL  
A1A_1 A2A_2 \cdots ANA_N  
QQ  
Query1\text{Query}_1  
Query2\text{Query}_2  
\vdots  
QueryQ\text{Query}_Q 

ただし、Queryi\text{Query}_i (1iQ1≤i≤Q) は ii 個目のクエリを表す。各クエリは以下の形式で与えられる。

ll rr
  • 入力は全て整数
  • 1N2.5×1031≤N≤2.5\times 10^3
  • 1KN1≤K≤N
  • 1L1≤L
  • 1AiN1≤A_i≤N (1iN1≤i≤N)
  • 1Q2.5×1051≤Q≤2.5\times 10^5
  • 各クエリについて、1lrN,  rl+1K,  L(rlK+2)(rlK+3)21≤l≤r≤N,\ \ r - l + 1≥K,\ \ L≤\frac{(r-l-K+2)(r-l-K+3)}{2}

また、N=5000N = 5000 の evil ケースが存在する。このテストケースは提出結果には影響しない。

出力

QQ 行出力せよ。ii 行目 (1iQ1≤i≤Q) には ii 個目のクエリに対する答えを出力せよ。

サンプル

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

(3,1,2,4)(3, 1, 2, 4) の長さ K(=3)K (= 3) 以上の連続部分列は (3,1,2),(1,2,4),(3,1,2,4)(3, 1, 2), (1, 2, 4), (3, 1, 2, 4)33 個です。これらの KK 番目の数はそれぞれ 3,4,33, 4, 3 で、この中の L(=2)L (= 2) 番目の数は 33 です。

サンプル2
入力
4 3 1
3 1 2 4
3
1 3
2 4
1 4
出力
3
4
3
サンプル3
入力
15 4 6
8 5 6 6 2 1 14 8 9 3 5 4 2 1 7
12
1 6
4 15
7 15
5 13
3 13
3 8
6 11
6 13
2 12
3 11
8 14
1 7
出力
8
3
4
5
4
14
14
5
5
6
5
6

出典

CPCTF22

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