Description

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$.

Input Format

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.

Output Format

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

12 6
1 1 4 5 1 4 2 2 5 2 3 3
1 1 3 7 9
1 2 3 5 6
1 1 3 2 4
0 7 1
1 1 4 2 5
1 5 7 8 10

YES
YES
NO
YES
YES

Hint

• 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