P5604 Little O and Permutations

Little O is a high school student who loves mathematics. He is now confused about a problem related to permutations. Please help him! **Note: The input format has been changed. The second and third lines have been swapped. (Please follow the current statement.)**

Little O has a permutation $p$ of length $n$. His good friend $\texttt{euei}$ has a sequence $a$ of length $n$, with values in $[1, n]$. One day, Little O suddenly wondered whether there exists a pair of indices $i, j$ such that $l \le i, j \le r$ and $p_{a_i} = a_j$. He solved this problem easily. However, $\texttt{euei}$ sometimes modifies the value at some position in this sequence, and also asks the above question for many different pairs $l, r$. Now Little O does not know how to handle it. Can you, the smart one, help Little O solve this problem?

The first line contains two positive integers $n, m$, where $m$ is the total number of modifications and queries. The second line contains $n$ positive integers $p_1, p_2, \cdots, p_n$, representing the permutation $p$. The third line contains $n$ positive integers $a_1, a_2, \cdots, a_n$, representing the initial sequence $a$. The next $m$ lines each contain three positive integers, in one of the following two formats: - `1 i v`, meaning set $a_i$ to $v$. - `2 l r`, meaning query whether there exists a pair of indices $i, j$ such that $l \le i, j \le r$ and $p_{a_i} = a_j$.

For each query, if such a pair exists, output `Yes`; otherwise output `No`.

**Hint** The input size is large, so please use a fast input method. **Explanation of the samples** For the first query, the pair $2, 3$ satisfies the requirement. For the second query, no pair satisfies the requirement. **Constraints** This problem has $5$ subtasks. You must pass all test points within a subtask to get the score for that subtask. For all testdata, $1 \le n,m \le 5\times 10^5$, $1 \le a_i, i, v, l, r \le n$, $p_i \neq i$. | # | Score | $n, m$ | Special Properties | Time Limit | | ---- | ----- | ---------------- | ------------------------------------- | ----------- | | 1 | 7 | $\leqslant 300$ | | $\text{1s}$ | | 2 | 23 | $\leqslant 2000$ | | $\text{1s}$ | | 3 | 15 | | No `1` operations | $\text{3s}$ | | 4 | 15 | | In each query, sequence $a$ is a permutation | $\text{3s}$ | | 5 | 40 | | | $\text{3s}$ | Blank entries in the table mean there are no special restrictions for that item. Translated by ChatGPT 5