P6498 [COCI 2016/2017 #2] Zamjene

**Warning: Abusing the judging system for this problem will result in your account being banned.**

Dominik builds an array $p_1,p_2,\dots,p_n$ with $n$ elements, and the array $q_1,q_2,\dots,q_n$ obtained by sorting it. He also defines a “swappable set”. If an unordered pair $(a,b)$ belongs to the “swappable set”, then he can swap the positions of $p_a$ and $p_b$. “Using the swappable set” means **performing a number of such swaps**. There are four operations: - Operation $1$: Format: `1 a b`. Swap $p_a$ and $p_b$ (not restricted by the “swappable set”). - Operation $2$: Format: `2 a b`. Add the unordered pair $(a,b)$ to the “swappable set”. - Operation $3$: Format: `3`. Determine whether the array $p$ can be sorted using the “swappable set”. - Operation $4$: Format: `4`. If the $x$-th element in array $p$ can be moved to position $y$ using the “swappable set”, then $x$ and $y$ are said to be connected. Here $x$ may be equal to $y$. The set of all $y$ connected to $x$ is called the “cloud” of $x$. If a “cloud” can use the “swappable set” to make every $i$ in the “cloud” satisfy $p_i=q_i$, then this “cloud” is called an “auspicious cloud”. Compute how many unordered pairs $(a,b)$ satisfy: - $1\le a,b\le n$ and $a\not=b$. - $a$ and $b$ are not connected. - Neither the “cloud” of $a$ nor the “cloud” of $b$ is an “auspicious cloud”. - After adding the unordered pair $(a,b)$ to the “swappable set”, the “cloud” of $a$ becomes an “auspicious cloud”. Please help Dominik complete these operations.

The first line contains two integers $n,q$, representing the number of elements in array $p$ and the number of operations. The second line contains $n$ integers $p_i$. The next $q$ lines are given in the following format: 1. An integer $t$, representing the type of the operation. 2. If $t$ is $1$ or $2$, then two distinct integers $a,b$ follow.

- For each operation $3$: If the array $p$ can be sorted using the “swappable set”, output one line `DA`. Otherwise, output one line `NE`. - For each operation $4$: Output one line with an integer, representing the number of unordered pairs $(a,b)$ that satisfy the conditions.

#### Sample 1 Explanation - The first operation: only the unordered pair $(2,3)$ satisfies the requirement. - The second operation: the array $p$ cannot be sorted using the “swappable set”. - The third operation: add the unordered pair $(2,3)$ to the “swappable set”. - The fourth operation: there is no unordered pair that satisfies the requirement. - The fifth operation: swap $p_2$ and $p_3$, and then the array $p$ can be sorted using the “swappable set”. ------------ #### Constraints For $100\%$ of the data, $1\le n,q\le 10^6$, $1\le p_i\le 10^6$, $1\le t\le 4$, $1\le a,b\le n$ and $a\not=b$. ------------ #### Notes **This problem is translated from [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #2](https://hsin.hr/coci/archive/2016_2017/contest2_tasks.pdf) _T5 Zamjene_.** Translated by ChatGPT 5