問題一覧 > 通常問題

No.1471 Sort Queries

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 165
作問者 : 蜜蜂蜜蜂 / テスター : MitarushiMitarushi nok0nok0
9 ProblemId : 5563 / 出題時の順位表
問題文最終更新日: 2021-04-09 23:37:10

問題文

$N$ 文字の英小文字からなる文字列 $S$ が与えられます。

$Q$ 個のクエリを処理してください。

$i$ 番目のクエリの内容は以下の通りです。
$S$ の $L_i$ 文字目から $R_i$ 文字目までから成る部分文字列を任意に並べ替えたものの中で辞書順最小である文字列の $X_i$ 文字目を出力してください。

入力

$N\ \ Q$
$S$
$L_1\ \ R_1\ \ X_1$
$L_2\ \ R_2\ \ X_2$
$\ \vdots$
$L_Q\ \ R_Q\ \ X_Q$

  • $S$ は英小文字のみからなる長さ $N$ の文字列
  • $ 1 \leq N,Q \leq 10^4$
  • $ 1 \leq L_i \leq R_i \leq N(1\leq i \leq Q)$
  • $ 1 \leq X_i \leq R_i-L_i+1(1\leq i \leq Q)$
  • $S$ 以外の入力はすべて整数

出力

$Q$ 行出力してください。 $i$ 行目には $i$ 番目のクエリに対する答えを出力し、改行してください。

サンプル

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

$1$ 番目のクエリについて考えます。

$S$ の $2$ 文字目から $4$ 文字目までからなる部分文字列は uer であり、これの並び替えのうち、辞書順最小のものは eru です。
これの $2$ 文字目である r を出力します。

サンプル2
入力
10 4
japanjapan
1 10 5
3 7 1
4 9 2
2 2 1
出力
j
a
a
a

サンプル3
入力
16 6
amazingmightyyyy
1 5 4
2 16 1
8 9 1
2 2 1
1 16 2
4 10 4
出力
m
a
i
m
a
i

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