English · Original
Chinese · Translation
Formal · Original
Anton likes permutations, especially he likes to permute their elements. Note that a permutation of _n_ elements is a sequence of numbers {_a_1, _a_2, ..., _a__n_}, in which every number from 1 to _n_ appears exactly once.
One day Anton got a new permutation and started to play with it. He does the following operation _q_ times: he takes two elements of the permutation and swaps these elements. After each operation he asks his friend Vanya, how many inversions there are in the new permutation. The number of inversions in a permutation is the number of distinct pairs (_i_, _j_) such that 1 ≤ _i_ < _j_ ≤ _n_ and _a__i_ > _a__j_.
Vanya is tired of answering Anton's silly questions. So he asked you to write a program that would answer these questions instead of him.
Initially Anton's permutation was {1, 2, ..., _n_}, that is _a__i_ = _i_ for all _i_ such that 1 ≤ _i_ ≤ _n_.
## Input
The first line of the input contains two integers _n_ and _q_ (1 ≤ _n_ ≤ 200 000, 1 ≤ _q_ ≤ 50 000) — the length of the permutation and the number of operations that Anton does.
Each of the following _q_ lines of the input contains two integers _l__i_ and _r__i_ (1 ≤ _l__i_, _r__i_ ≤ _n_) — the indices of elements that Anton swaps during the _i_\-th operation. Note that indices of elements that Anton swaps during the _i_\-th operation can coincide. Elements in the permutation are numbered starting with one.
## Output
Output _q_ lines. The _i_\-th line of the output is the number of inversions in the Anton's permutation after the _i_\-th operation.
[samples]
## Note
Consider the first sample.
After the first Anton's operation the permutation will be {1, 2, 3, 5, 4}. There is only one inversion in it: (4, 5).
After the second Anton's operation the permutation will be {1, 5, 3, 2, 4}. There are four inversions: (2, 3), (2, 4), (2, 5) and (3, 4).
After the third Anton's operation the permutation will be {1, 4, 3, 2, 5}. There are three inversions: (2, 3), (2, 4) and (3, 4).
After the fourth Anton's operation the permutation doesn't change, so there are still three inversions.
Anton 喜欢排列，尤其喜欢交换排列中的元素。注意，一个包含 #cf_span[n] 个元素的排列是一个序列 #cf_span[{a1, a2, ..., an}]，其中从 #cf_span[1] 到 #cf_span[n] 的每个数恰好出现一次。
某天，Anton 得到了一个新的排列并开始玩它。他执行以下操作 #cf_span[q] 次：他选取排列中的两个元素并交换它们。每次操作后，他都会问他的朋友 Vanya，当前排列中有多少个逆序对。一个排列中的逆序对数量是指满足 #cf_span[1 ≤ i < j ≤ n] 且 #cf_span[ai > aj] 的不同对 #cf_span[(i, j)] 的数量。
Vanya 疲于回答 Anton 的愚蠢问题，因此他请你写一个程序来代替他回答这些问题。
最初，Anton 的排列是 #cf_span[{1, 2, ..., n}]，即对于所有满足 #cf_span[1 ≤ i ≤ n] 的 #cf_span[i]，都有 #cf_span[ai = i]。
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[q] #cf_span[(1 ≤ n ≤ 200 000, 1 ≤ q ≤ 50 000)] —— 分别表示排列的长度和 Anton 执行的操作次数。
接下来的 #cf_span[q] 行，每行包含两个整数 #cf_span[li] 和 #cf_span[ri] #cf_span[(1 ≤ li, ri ≤ n)] —— 表示 Anton 在第 #cf_span[i] 次操作中交换的两个元素的下标。注意，第 #cf_span[i] 次操作中交换的两个元素下标可能相同。排列中的元素从 1 开始编号。
请输出 #cf_span[q] 行。第 #cf_span[i] 行输出的是 Anton 执行第 #cf_span[i] 次操作后排列中的逆序对数量。
考虑第一个样例。
第一次操作后，排列变为 #cf_span[{1, 2, 3, 5, 4}]。其中只有一个逆序对：#cf_span[(4, 5)]。
第二次操作后，排列变为 #cf_span[{1, 5, 3, 2, 4}]。其中有四个逆序对：#cf_span[(2, 3)]、#cf_span[(2, 4)]、#cf_span[(2, 5)] 和 #cf_span[(3, 4)]。
第三次操作后，排列变为 #cf_span[{1, 4, 3, 2, 5}]。其中有三个逆序对：#cf_span[(2, 3)]、#cf_span[(2, 4)] 和 #cf_span[(3, 4)]。
第四次操作后，排列不变，因此仍然有三个逆序对。
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[q] #cf_span[(1 ≤ n ≤ 200 000, 1 ≤ q ≤ 50 000)] —— 分别表示排列的长度和 Anton 执行的操作次数。接下来的 #cf_span[q] 行，每行包含两个整数 #cf_span[li] 和 #cf_span[ri] #cf_span[(1 ≤ li, ri ≤ n)] —— 表示 Anton 在第 #cf_span[i] 次操作中交换的两个元素的下标。注意，第 #cf_span[i] 次操作中交换的两个元素下标可能相同。排列中的元素从 1 开始编号。
## Output
请输出 #cf_span[q] 行。第 #cf_span[i] 行输出的是 Anton 执行第 #cf_span[i] 次操作后排列中的逆序对数量。
[samples]
## Note
考虑第一个样例。
第一次操作后，排列变为 #cf_span[{1, 2, 3, 5, 4}]。其中只有一个逆序对：#cf_span[(4, 5)]。
第二次操作后，排列变为 #cf_span[{1, 5, 3, 2, 4}]。其中有四个逆序对：#cf_span[(2, 3)]、#cf_span[(2, 4)]、#cf_span[(2, 5)] 和 #cf_span[(3, 4)]。
第三次操作后，排列变为 #cf_span[{1, 4, 3, 2, 5}]。其中有三个逆序对：#cf_span[(2, 3)]、#cf_span[(2, 4)] 和 #cf_span[(3, 4)]。
第四次操作后，排列不变，因此仍然有三个逆序对。
**Definitions**
Let $ n, q \in \mathbb{Z}^+ $ denote the length of the permutation and the number of swap operations.
Let $ \pi^{(0)} = (1, 2, \dots, n) $ be the initial permutation.
For $ k \in \{1, \dots, q\} $, let $ \pi^{(k)} $ be the permutation after the $ k $-th swap operation.
Each operation swaps elements at positions $ l_k $ and $ r_k $:
$ \pi^{(k)} = \pi^{(k-1)} \circ \tau_{l_k, r_k} $, where $ \tau_{i,j} $ swaps elements at indices $ i $ and $ j $.
**Constraints**
1. $ 1 \leq n \leq 200{,}000 $
2. $ 1 \leq q \leq 50{,}000 $
3. For each $ k \in \{1, \dots, q\} $: $ 1 \leq l_k, r_k \leq n $
**Objective**
For each $ k \in \{1, \dots, q\} $, compute the number of inversions in $ \pi^{(k)} $:
$$
I_k = \left| \left\{ (i, j) \mid 1 \leq i < j \leq n \text{ and } \pi^{(k)}_i > \pi^{(k)}_j \right\} \right|
$$
Output $ I_1, I_2, \dots, I_q $.
API Response (JSON)
{
"problem": {
"name": "E. Anton and Permutation",
"description": {
"content": "Anton likes permutations, especially he likes to permute their elements. Note that a permutation of _n_ elements is a sequence of numbers {_a_1, _a_2, ..., _a__n_}, in which every number from 1 to _n_",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 4000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF785E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Anton likes permutations, especially he likes to permute their elements. Note that a permutation of _n_ elements is a sequence of numbers {_a_1, _a_2, ..., _a__n_}, in which every number from 1 to _n_...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Anton 喜欢排列，尤其喜欢交换排列中的元素。注意，一个包含 #cf_span[n] 个元素的排列是一个序列 #cf_span[{a1, a2, ..., an}]，其中从 #cf_span[1] 到 #cf_span[n] 的每个数恰好出现一次。\n\n某天，Anton 得到了一个新的排列并开始玩它。他执行以下操作 #cf_span[q] 次：他选取排列中的两个元素并交换它们。每次操作后，他都会问...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, q \\in \\mathbb{Z}^+ $ denote the length of the permutation and the number of swap operations. \nLet $ \\pi^{(0)} = (1, 2, \\dots, n) $ be the initial permutation. \nFor $ k \\in...",
"is_translate": false,
"language": "Formal"
}
]
}