시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
6 초 | 512 MB | 10 | 3 | 3 | 50.000% |
Dominik has envisioned an array of positive integers p1, …, pn. Let’s denote the sorted version of that array as q1, …, qn.
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:
You must answer how many pairs of different positions (A, B) exist such that it holds:
Please note: Pairs (A, B) and (B, A) are considered an identical pair.
The first line of input contains integers N and Q (1 ≤ N, Q ≤ 1 000 000).
The second line of input contains N integers p1, …, pn (1 ≤ p1, …, pn ≤ 1 000 000).
Each of the following Q lines contains a query in the following format:
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 non-negative integer from the task.
3 5 1 3 2 4 3 2 2 3 4 3
1 NE 0 DA
5 5 4 2 1 4 4 3 4 1 1 3 3 4
NE 1 DA 0
4 10 2 1 4 3 3 4 1 1 2 3 4 2 2 3 2 1 2 4 2 3 4 3
NE 2 NE 1 3 DA
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).