| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 24 | 12 | 12 | 60.000% |
Irma works in a library. Every day she watches visitors take a couple of books from the bookshelf, read them, and put books back in the same places they took them. Usually people mess up the order and swap two books they read. Let's take a look at one specific bookshelf with $n$ books in some order, numbered from 1ドル$ to $n$ from left to right. The $i$-th visitor takes books from positions $x_i$ and $y_i$ and puts them back on the same positions, but in the wrong order. After the $i$-th visitor, the book that was at $x_i$ is now at position $y_i$ and vice versa.
In the evening, after the library is closed, Irma wants to put all the books back on their places. For each book there is a number $p_i$ --- a position where that book should end up in the end. To rearrange books, Irma can take any book from the shelf and insert it in the beginning or in the end (so it ends up in the first or in the last place on the shelf).
What is the minimum number of moves Irma can do to put all books in order? Answer this question for some initial placement of books, determined by $p_i,ドル and after each visitor that swapped places of some two books.
The first line contains two integers $n$ and $q$ (2ドル \le n \le 2 \cdot 10^5$; 0ドル \le q \le 2 \cdot 10^5$) --- the number of books on the shelf and the number of visitors. The next line contains $n$ distinct integers $p_i$ (1ドル \le p_i \le n$), meaning that the book in the $i$-th position must end up in position $p_i$.
Next $q$ lines describe library's visitors. Each line contains two integers $x_i,ドル $y_i$ (1ドル \le x_i < y_i \le n$), that mean that the $i$-th visitor swapped two books on positions $x_i$ and $y_i$.
Print $q + 1$ integers --- the minimum number of moves required to sort all books for the initial order, then for the order the after the first visitor, \ldots, after all $q$ visitors.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $n, q \le 8$ |
| 2 | 15 | $n, q \le 200$ |
| 3 | 15 | $n \le 2000$; $q = 0$ |
| 4 | 15 | $n, q \le 2000$ |
| 5 | 20 | $n \le 2 \cdot 10^5$; $q = 0$ |
| 6 | 25 | $n, q \le 2 \cdot 10^5$ |
5 2 5 1 2 4 3 4 5 1 4
2 1 3
The initial order of books is $(5, 1, 2, 4, 3)$. To sort these books out, first, put the book 4ドル$ in the end, then do the same with book 5ドル$. After the first visitor, the bookshelf now looks like $(5, 1, 2, 3, 4)$; it's enough to just move the book 5ドル$ to the end. After the second visitor the order of books is $(3, 1, 2, 5, 4)$. For this order the minimum number of moves is 3ドル,ドル there are several ways to achieve the final order in 3ドル$ moves.