P7879 「SWTR-7」How to AK NOI?

Some definitions and conventions about strings are explained in the “Help / Hint” section. Please do not maliciously exploit the judge. --- Xiao A is reading an article — “How to AK NOI Elegantly?”.

Unfortunately, this article is written in English. Xiao A has very poor eyesight, and his vocabulary is also very small. Specifically, this article can be represented by a string $t$. Another string $s$ is given: every word that Xiao A knows is a substring of $s$ with length **at least $k$**. A text segment $T$ is called “readable” if and only if it can be split into several words that Xiao A can understand. For example, when $k=2$ and $s=\texttt{abcd}$, $\texttt{abcd/abc}$ and $\texttt{cd/ab/bc/bcd}$ are readable, while $\texttt{abcc}$ and $\texttt{tzcaknoi}$ are not readable. Next, Xiao A will perform $q$ actions: - Type 1: Rub his eyes. Specifically, Xiao A chooses a substring $t[l:r]$ of the article $t$ and modifies it into a string $x\ (|x|=r-l+1)$. - Type 2: Read the article. Specifically, Xiao A chooses a substring $t[l:r]$ of the article $t$ and reads it. **For each Type 2 operation, you need to tell Xiao A whether he can understand this text segment**. If he can understand it, output `Yes`; otherwise output `No`.

The first line contains a positive integer $T$, indicating the Subtask ID for this test point. The second line contains a string $s$. The third line contains a string $t$. The fourth line contains a positive integer $k$. The fifth line contains a positive integer $q$. The next $q$ lines each describe one query. First, an operation parameter $op$ is given: - If $op=1$, then two positive integers $l,r$ and a string $x$ follow, meaning to modify $t[l:r]$ into $x$. - If $op=2$, then two positive integers $l,r$ follow, meaning one query.

For each query, output one line: if it is readable, output `Yes`; otherwise output `No`.

**“Constraints and Conventions”** Let $n=|s|$, $m=|t|$, $L=\sum |x|$. | Subtask | $n\leq$ | $m\leq$ | $L\leq$ | $q\leq$ | $k\leq$ | Score | | :-----: | :------------: | :-----: | :-----: | :-----: | :-----: | :------: | | 0 | | | | | | 0 point | | 1 | $70$ | $70$ | | $70$ | | 10 points | | 2 | $200$ | $200$ | | $200$ | | 10 points | | 3 | $10^3$ | $10^3$ | | $10^3$ | | 10 points | | 4 | | | | | $1$ | 10 points | | 5 | $2\times 10^5$ | $10^5$ | $0$ | $2\times 10^4$ | $5$ | 15 points | | 6 | $2\times 10^5$ | $10^5$ | $5\times 10^4$ | $2\times 10^4$ | $5$ | 10 points | | 7 | | | | | $6$ | 15 points | | 8 | | | | | | 20 points | For $100\%$ of the data: $1\leq n\leq 3\times 10^6$, $1\leq L\leq 3\times 10^5$, $1\leq m\leq 2\times 10^5$, $1\leq q\leq 10^5$, $1\leq k\leq 8$. It is guaranteed that $|x|=r-l+1$, and the character set is $[\texttt{a,i}]$. --- Subtask 0 contains the sample and **Hack testdata**. - Subtask 0 ~ 3: time limit 1s. - Subtask 4 ~ 6: time limit 1.5s. - Subtask 7: time limit 3s. - Subtask 8: time limit 4.5s. **“Subtask Dependencies”** **This problem uses subtask dependencies**. Simply put, if Subtask a depends on Subtask b, then **Subtask a will be counted toward the total score only when you pass all test points of Subtask b**. - Subtask 1 depends on Subtask 0. - Subtask 2 depends on Subtask 0,1. - Subtask 3 depends on Subtask 0,1,2. - Subtask 6 depends on Subtask 0,5. - Subtask 7 depends on Subtask 0,5,6. - Subtask 8 depends on Subtask 0~7. **It is guaranteed that the Hack testdata of Subtask 0 satisfies all constraints of Subtask 1,2,3,6,7,8**. **“Help / Hint”** A string $t'$ is a substring of $t$ if and only if we can delete some characters (possibly none) from the beginning and the end of $t$ and obtain $t'$. Define $t[l:r]$ as the string formed by $t_lt_{l+1}\cdots t_{r-1}t_r$. The input file is large, so please pay attention to IO optimization. **“Source”** [Sweet Round 07](https://www.luogu.com.cn/contest/51773) E. idea & solution & data: [Alex_Wei](https://www.luogu.com.cn/user/123294); problem checking: [tzc_wk](https://www.luogu.com.cn/user/115194). Translated by ChatGPT 5