問題一覧 > 通常問題

No.3638 Itsuki

レベル : / AI推定難易度 : 825 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 26
作問者 : kazuppa / テスター : Unbakedbread Tamiji153
お気に入りにしたユーザー ProblemId : 13605 / 自分の提出
問題文最終更新日: 2026-08-25 18:36:14
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Paken新入生コンday2 (順位表) の他の問題:

Problem Statement

You are given a string $S$ of length $N$ consisting of lowercase English letters.

A total of $Q$ queries of the following $2$ types will be given. Process them in order.

  • 1 i c　Update the $i$-th character of $S$ to $c$.
  • 2 t　Answer whether $S$ contains $t$ as a substring.

Here, we say that $s$ contains $t$ as a substring when a string $s'$, obtained by deleting $0$ or more characters from the beginning and $0$ or more characters from the end of the string $s$, is equal to $t$.

Constraints

  • $1\leq N,Q\leq 5\times 10^3$
  • $S$ is a string of length $N$ consisting of lowercase English letters
  • In queries of type $1$, $1\leq i\leq N$
  • In queries of type $1$, $c$ is a lowercase English letter
  • In queries of type $2$, $t$ is a string consisting of lowercase English letters whose length is at least $1$ and at most $10^3$
  • Queries of type $2$ are given at least 1 time
  • All numbers given in the input are integers

Subtasks

This problem has partial scoring by subtasks.

Subtask Name Score Constraints
Subtask 110 %$N=1$
Subtask 250 %Queries of type $1$ are not given
Subtask 340 %No additional constraints

Input

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

Here, each $Query$ is given in one of the following forms:

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

.

Output

When query 2 is given $t$ times, print $t$ lines.

On the $i\ (1\leq i\leq t)$-th line, output the answer to the $i$-th given query 2. Print Yes if the string is contained, and No if it is not.

Sample

Sample 1
Input
5 5
abcde
2 ac
2 bf
1 3 f
2 ac
2 bf
Output
No
No
No
Yes

Before processing the 3rd query, $S=$abcde. At this point, $S$ contains neither ac nor bf as a substring.

After processing the 3rd query, $S=$abfde. At this point, $S$ does not contain ac as a substring, but it does contain bf as a substring.

Sample 2
Input
7 7
aitsuki
2 aitsuki
2 itsuki
2 azki
1 4 z
2 aitsuki
2 itsuki
2 azki
Output
Yes
Yes
No
No
No
No

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