問題一覧 > 通常問題

No.3638 Itsuki

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 : kazuppa / テスター : Unbakedbread Tamiji153
ProblemId : 13605 / Paken新入生コンday2 (順位表) / 自分の提出
問題文最終更新日: 2026-08-25 18:36:14
Paken新入生コンday2の他の問題:

問題文

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

これから以下の $2$ 種類のクエリが合計 $Q$ 個与えられます。順に処理してください。

  • 1 i c　$S$ の $i$ 文字目を $c$ に更新する。
  • 2 t　$S$ が部分文字列に $t$ を含むか答える。

ここで、文字列 $s$ を先頭から $0$ 文字以上、末尾から $0$ 文字以上削除した文字列 $s'$ が $t$ と一致するとき、 $s$ が部分文字列に $t$ を含むと定義します。

制約

  • $1\leq N,Q\leq 5\times 10^3$
  • $S$ は英小文字からなる長さ $N$ の文字列
  • $1$ 種類目のクエリにおいて、$1\leq i\leq N$
  • $1$ 種類目のクエリにおいて、$c$ は英小文字
  • $2$ 種類目のクエリにおいて、$t$ は英小文字からなる長さ $1$ 以上 $10^3$ 以下の文字列
  • $2$ 種類目のクエリは1回以上与えられる
  • 入力で与えられる数字は全て整数

小課題

この問題にはサブタスクによる部分点が設定されています。

小課題名 配点 制約
小課題110 %$N=1$
小課題250 %$1$ 種類目のクエリは与えられない
小課題340 %追加の制約はない

入力

$N\ Q$
$S$
$Query_1$
$Query_2$
$\vdots$
$Query_Q$

また、$Query$ は

$1\ i\ c$
$2\ t$

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

出力

クエリ2が与えられる回数が $t$ 回である時、$t$ 行出力してください。

$i\ (1\leq i\leq t)$ 行目には $i$ 番目に与えられたクエリ2に答えてください。含むなら Yes、含まないなら No を出力してください。

サンプル

サンプル1
入力
5 5
abcde
2 ac
2 bf
1 3 f
2 ac
2 bf
出力
No
No
No
Yes

3つ目のクエリを処理する前、$S=$abcde です。この時、$S$ は ac も bf も部分文字列に含んでいません。

3つ目のクエリを処理した後、$S=$abfde です。この時、$S$ は ac を部分文字列に含んでいませんが bf は部分文字列に含んでいます。

サンプル2
入力
7 7
aitsuki
2 aitsuki
2 itsuki
2 azki
1 4 z
2 aitsuki
2 itsuki
2 azki
出力
Yes
Yes
No
No
No
No

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