P2448 Endless Life

Time flows on like this, never stopping day or night! Ye Liangchen (叶良辰) believes his lifespan is infinite, and he improves every day. On the first day of Ye Liangchen’s life, he has $1$ point of ability. On the second day, he has $2$ points. On day $n$, he has $n$ points. That is, $S_i = i$. However, the mischievous Xiao A (小 A) uses a time machine and tells him that on day $x$ and day $y$, he can arbitrarily swap the ability values of any two days, i.e., $S_x \leftrightarrow S_y$. Xiao A plays and plays, and finally gets bored. Ye Liangchen: Xiao A, just you wait. I have $100$ ways to make you wish you were dead. Unless you can tell me within $1$ second how many pairs are “abnormal pairs.” That is, in the final ability sequence, how many pairs of days $x, y$ with $x < y$ satisfy $S_x > S_y$? Xiao A: I’m so scared. So he comes to you.

The first line contains an integer $k$, indicating how many times Xiao A used the time machine. The next $k$ lines each contain $x_i, y_i$, meaning $S_{x_i}$ and $S_{y_i}$ are swapped.

Output a single line: the number of “abnormal pairs.”

Sample explanation - Initially it is $1,2,3,4,5,6\cdots$. - Then it becomes $1,4,3,2,5,6\cdots$. - Then it becomes $2,4,3,1,5,6\cdots$. The matching pairs are $(1,4)$, $(2,3)$, $(2,4)$, $(3,4)$. Constraints - For $30\%$ of the testdata, $x_i, y_i \le 2 \times 10^3$. - For $70\%$ of the testdata, $x_i, y_i \le 10^5$. - For $100\%$ of the testdata, $x_i, y_i \le 2^{31} - 1$, $k \le 10^5$. Translated by ChatGPT 5