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