P6688 Multiset.

You are given a non-negative integer sequence $a_1,a_2,a_3,\ldots, a_n$ of length $n$, and $q$ operations. Each operation first gives a parameter $op$: - If $op=0$, then two parameters $x,y$ are given, and you need to modify $a_x$ to $y$. - If $op=1$, then four parameters $l_1,r_1,l_2,r_2$ are given (it is guaranteed that $r_1-l_1=r_2-l_2$). You need to determine whether the interval $[l_1,r_1]$ and the interval $[l_2,r_2]$ are essentially the same. If they are, output `YES`, otherwise output `NO`. Definition of being essentially the same: let the interval length be $\text{len}$. Let the sequence $p_{1}\dots p_{\text{len}}$ be the result of sorting $a_{l_1}\dots a_{r_1}$ in non-decreasing order, and let the sequence $q_{1}\dots q_\text{len}$ be the result of sorting $a_{l_2}\dots a_{r_2}$ in non-decreasing order. There exists an integer $k$ such that $\forall i,p_i+k=q_i$.

The first line contains two positive integers $n,q$, representing the length of the sequence and the number of operations. The second line contains $n$ non-negative integers, representing $a_{1},a_2,a_3,\ldots,a_n$. The next $q$ lines each describe one of the operations above.

For each operation with $op=1$, output whether the two intervals are essentially the same. If yes, output `YES`, otherwise output `NO`.

- Subtask 1 ($25$ pts): $1\leq n,q \leq 1000$. - Subtask 2 ($25$ pts): $1\leq n,q \leq 10^5$, $0\leq a_i,y\leq 100$. - Subtask 3 ($25$ pts): $1\leq n,q \leq 10^5$. - Subtask 4 ($25$ pts): no special constraints. You can only get the score of a subtask if you pass all testdata in that subtask. For all data: $1\leq n,q \leq 10^6$, $1\leq x \leq n$, $0\leq a_i,y \leq 10^6$. Also, for all $l,r$, $1\leq l\leq r\leq n$. Translated by ChatGPT 5