Olympic Chuyên KHTN 2020 - Ngày 1 - Bài 2 - PERMSWAP

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Cho dãy ~P~ là một hoán vị của ~{1 \dots N}~. Gọi ~F(P)~ là số bước ít nhất để đưa ~P~ về dãy ~\{1 \dots N\}~, trong đó mỗi bước được phép chọn hai vị trí ~i~, ~j~ và đổi chỗ giá trị ~P[i]~ và ~P[j]~.

Cho ~C~ truy vấn đổi chỗ ~P[x]~ và ~P[y]~, sau mỗi truy vấn in ra ~F(P)~. Mọi phép đổi chỗ là cố định, tức là sau mỗi truy vấn ~P~ không quay trở lại như cũ.

Input

Dòng ~1~: ~2~ số ~N~ và ~C~

Dòng ~2~: ~N~ số ~P[1]~, ~P[2]~, ~\dots~, ~P[N]~ là dãy ~P~ ban đầu

Dòng ~2 + i~: ~2~ số ~x~, ~y~ là tham số của truy vấn thứ ~i~

Output

In ra ~C~ dòng, dòng thứ ~i~ in ~1~ số duy nhất là ~F(P)~ sau truy vấn thứ ~i~.

Giới hạn

  • ~2 \leq N \leq 10^5~, ~1 \leq C \leq 5 \times 10^4~, ~1 \leq x < y \leq N~
  • ~25\%~: ~N~, ~C \leq 10^3~
  • ~75\%~: Không có ràng buộc gì thêm

Sample Input 1

3 2
2 3 1
2 3
2 3

Sample Output 1

1
2

Sample Input 2

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

Sample Output 2

3
2
1

Giải thích

Test ~1~: ~P = {2, 3, 1} \rightarrow {2, 1, 3} \rightarrow {2, 3, 1}~


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.