6 \(s / 512\) \(MB / 140\) points

Dominik has envisioned an array of positive integers \(p\)

1

, ..., \(p\)

\(n\)

. Let’s denote the sorted
version of that array as \(q\)

1

, ..., \(q\)

\(n\)

.

Also, he envisioned a set of allowed substitutions. If a pair ( \(X\)

, \(Y\)

) is a member of the set of
allowed substitutions, Dominik can swap the numbers at positions \(X\)

and \(Y\)

in array \(p\)

.

Marin is giving Dominik \(Q\)

queries, and each of them is of one of the following types:

1.
Swap numbers at positions \(A\)

and \(B\)

.
2.
Add pair ( \(A\)

, \(B\)

) to the set of allowed substitutions.
Marin can give pair ( \(A\)

, \(B\)

) that is already in the set of allowed substitutions.
3.
See if it’s possible to sort the array using only the allowed substitutions?
The substitutions can be used in an arbitrary order, and each substitution can be
made an arbitrary number of times.
4.
Let’s call a pair of positions ( \(A\)

, \(B\)

) linked if the number from position \(A\)

is possible to
transfer to position \(B\)

using only allowed subtitutions.
Let’s call the set of all positions linked to position \(A\)

the cloud of \(A\)

.
A cloud is good if it’s possible for each position \(j\)

from the cloud to achieve \(p\)

\(j\)

= \(q\)

_{j}
using a series of allowed substitutions.

You must answer how many pairs of different positions ( \(A\)

, \(B\)

) exist such that it holds:
a.
Positions \(A\)

and \(B\)

are not linked
b.
Cloud of \(A\)

is not good and cloud of \(B\)

is not good
c.
If we add pair ( \(A\)

, \(B\)

) to the set of allowed substitutions, the cloud of \(A\)

(created
by linking the cloud of \(A\)

and cloud of \(B\)

) becomes good.

Please note: Pairs (A, B) and (B, A) are considered an identical pair.

In test cases worth 50% of total points, it will hold \(N\)

, \(Q\)

≤ 1 000.

6 \(s / 512\) \(MB / 140\) points

PRIMJERI TEST PODATAKA

input
input
input
3 5
1 3 2
4
3
2 2 3
4
3

5 5
4 2 1 4 4
3
4
1 1 3
3
4

4 10
2 1 4 3
3
4
1 1 2
3
4
2 2 3
2 1 2
4
2 3 4
3

output
output
output
1
NE
0
DA

NE
1
DA
0

NE
2
NE
1
3
DA

Clarification of the first test case:
The answer to the first query is 1 because the pair of positions (2, 3) meets all given requirements.
The answer to the second query is NE (no) because it is impossible to transfer numbers 2 and 3 to the
corresponding positions, because the set of allowed substitutions is empty.
After the third query, we add pair (2, 3) to the set of allowed substitutions.
The answer to the fourth query is now 0 because 2 and 3 are already linked, and the answer to the fifth
query is DA (yes), because it is possible to sort the array by applying the allowed substitution (2, 3).

The first line of input contains integers \(N\)

and \(Q\)

(1 ≤ \(N\)

, \(Q\)

≤ 1 000 000).
The second line of input contains \(N\)

integers \(p\)

1

, ..., \(p\)

\(n\)

_{ }^{(1 ≤}^{ }^{p}

1

, ..., \(p\)

\(n\)

≤ 1 000 000).
Each of the following \(Q\)

lines contains a query in the following format:
●
The first number in the line is the type of query \(T\)

from the set {1, 2, 3, 4}.
●
If the type of query \(T\)

is 1 or 2, two different integers \(A\)

and \(B\)

follow (1 ≤ \(A\)

, \(B\)

≤ \(N\)

)
that represent the substitution ( \(A\)

, \(B\)

).

For each query of type 3 or 4, output the answer in its separate line.
The answer to query of type 3 is “DA” (Croatian for yes) or “NE” (Croatian for no), without the
quotation marks, and the answer to query of type 4 is a n\(on-ne\)gative integer from the task.

생성자가 기록되지 않았습니다.

출처 COCI 2016/2017 Contest 2