CF785E Anton and Permutation

Anton 喜欢排列，尤其喜欢对排列中的元素进行调整。注意，一个长度为 $n$ 的排列是一个数列 ${a_{1},a_{2},...,a_{n}}$，其中每个 $1$ 到 $n$ 的数字都恰好出现一次。 有一天，Anton 得到一个新的排列，并开始玩耍。他进行了 $q$ 次如下操作：每次从排列中选取两个元素，交换它们。在每次操作之后，他都会问他的朋友 Vanya，现在这个排列中有多少个逆序对。排列中的逆序对，是指满足 $1 \leq i < j \leq n$ 且 $a_i > a_j$ 的不同的数对 $(i, j)$ 的个数。 Vanya 厌倦了回答 Anton 这些无聊的问题，于是请你写一个程序，帮他来解答。 一开始 Anton 的排列是 ${1, 2, ..., n}$，即对于所有的 $1 \leq i \leq n$，都有 $a_i = i$。

输入的第一行包含两个整数 $n$ 和 $q$，$1 \leq n \leq 200000$，$1 \leq q \leq 50000$，分别表示排列的长度和 Anton 进行的操作次数。 接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$，$1 \leq l_i, r_i \leq n$，表示 Anton 在第 $i$ 次操作中交换排列第 $l_i$ 个和第 $r_i$ 个元素。注意，在某次操作中，Anton 可能会交换同一个元素。排列中的元素编号从 1 开始。

输出共 $q$ 行，第 $i$ 行输出 Anton 在第 $i$ 次操作后当前排列中的逆序对个数。

考虑第一个样例。 第一次操作后，排列变为 ${1,2,3,5,4}$。只有一组逆序对：$(4,5)$。 第二次操作后，排列变为 ${1,5,3,2,4}$。有四组逆序对：$(2,3)$，$(2,4)$，$(2,5)$ 和 $(3,4)$。 第三次操作后，排列变为 ${1,4,3,2,5}$。有三组逆序对：$(2,3)$，$(2,4)$ 和 $(3,4)$。 第四次操作后，排列未发生变化，所以逆序对的个数仍为三对。 由 ChatGPT 5 翻译