P5821 [L&K R-03] Password String Matching

As everyone knows, Little L really likes to use $123321$ as a password. Every time he logs in to Codeforces, he sees a very eye-catching message: ```text Your password is extremely weak or has been leaked . Please, change it ASAP. (see https://haveibeenpwned.com/) ```

After getting destroyed by the judge, Little L reflected and decided to use a safer password. Little L designed a password that may be as long as $200{,}000$ characters and consists only of lowercase letters, and he guarantees that nobody can remember it, guess it, or brute-force it (including Little L himself). To avoid forgetting the whole password string (no need to avoid it; he has already forgotten it), Little L wrote a program that can store his password string $T$, but cannot output it directly (because others might use this program). The first time, Little L reconstructs a string $P$ of length $l$ from memory. Later, he will modify one character of $P$ based on the program’s output. This program can compute the **mismatch degree** between the current guess string $P$ and the substring of $T$ with the same length. Define the value of character `a` as $1$, character `b` as $2$, and so on, up to character `z` as $26$. Define the mismatch degree of two strings $s,t$ as the sum of the squares of the differences of their values at corresponding positions. Now, Little L wants to know whether his program is correct. Please write a similar program as well.

The first line contains three integers $n,l,m$, representing the length $n$ of the password string $T$, the length $l$ of the guess string $P$, and the number of operations $m$. The next two lines contain two strings, which are $T$ and $P$. The next $m$ lines each start with an integer $op$, indicating the type of operation: - If $op=1$, then an integer $x$ follows, meaning you need to query the mismatch degree between $P$ and the substring of $T$ of length $l$ starting from position $x$. - If $op=2$, then an integer $x$ and a character $c$ follow, meaning you modify the $x$-th character of $P$ to make it equal to $c$.

For each operation of type $1$, output one line containing the required value.

**Please note the special time limit of this problem.** **The data size is large, so please optimize constants carefully.** To prevent the problem from being too strict on runtime, this problem **provides [Bajuyang](https://www.luogu.com.cn/paste/ky1fh8zk)**. You can paste it directly at the very beginning of your code and submit. In this problem, all indices start from $1$. - Subtask \#1: $30$ points, guaranteed $n,m\le 5\times 10^3$. - Subtask \#2: $30$ points, guaranteed there is no operation type $2$. - Subtask \#3: $40$ points, guaranteed $n,m\le 2\times 10^5$. For $100\%$ of the testdata, it is guaranteed that $1\le l\le n$ and $1\le x$. For all operations of type $1$, it is guaranteed that $x-1+l\le n$. For all operations of type $2$, it is guaranteed that $x\le l$. ### Sample Explanation $(a-a)^2+(n-n)^2+(g-g)^2+(r-e)^2+(y-r)^2=13^2+7^2=218$. $(a-a)^2+(m-m)^2+(a-g)^2+(n-e)^2+(g-r)^2=6^2+9^2+11^2=238$。 Translated by ChatGPT 5