「Codeforces 785E」Anton and Permutation【树套树】

Time Limit: 4 Sec Memory Limit: 512 MB

Description

Anton likes permutations, especially he likes to permute their elements. Note that a permutation of nn elements is a sequence of numbers {a1,a2,an}\{a_1, a_2, \cdots a_n\}, in which every number from 11 to nn appears exactly once.

One day Anton got a new permutation and started to play with it. He does the following operation qq 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)(i, j) such that 1i<jn1 \leqslant i < j \leqslant n and ai>aja_i > a_j.

Vanya is tired of answering Anton\footnotesize 's silly questions. So he asked you to write a program that would answer these questions instead of him.

Initially Anton\footnotesize 's permutation was {1,2,n}\{1, 2, \cdots n\}, that is ai=ia_i = i for all ii such that 1in1 \leqslant i \leqslant n.

Input

The first line of the input contains two integers nn and qq (1n2000001 \leqslant n \leqslant 200000, 1q500001 \leqslant q \leqslant 50000) — the length of the permutation and the number of operations that Anton does.

Each of the following qq lines of the input contains two integers lil_i and rir_i (1li,rin1 \leqslant l_i, r_i \leqslant n) — the indices of elements that Anton swaps during the ii-th operation. Note that indices of elements that Anton swaps during the ii-th operation can coincide. Elements in the permutation are numbered starting with one.

Output

Output qq lines. The ii-th line of the output is the number of inversions in the Anton\footnotesize 's permutation after the ii-th operation.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Sample Input #1:
5 4
4 5
2 4
2 5
2 2

Sample Input #2:
6 7
1 4
3 5
2 3
3 3
3 6
2 1
5 1

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Sample Output #1:
1
4
3
3

Sample Output #2:
5
6
7
7
10
11
8

Hint

Consider the first sample.

After the first Anton\footnotesize 's operation the permutation will be {1,2,3,5,4}\{1, 2, 3, 5, 4\}. There is only one inversion in it: (4,5)(4, 5).

After the second Anton\footnotesize 's operation the permutation will be {1,5,3,2,4}\{1, 5, 3, 2, 4\}. There are four inversions: (2,3)(2, 3), (2,4)(2, 4), (2,5)(2, 5) and (3,4)(3, 4).

After the fourth Anton\footnotesize 's operation the permutation doesn\footnotesize 't change, so there are still three inversions.

Solution

每次交换两个数,可以看做将答案减去这两个数对答案的贡献,然后交换两数,最后将答案再加上这两个数对答案的贡献。而每一个数对答案的贡献,也就是在其位置之前比它大的数的个数,加上在其位置之后比它小的数的个数。

使用树状数组套线段树来维护。树状数组维护的是位置,且每个节点包含一个权值线段树。如果直接用权值线段树空间会超出限制,所以线段树要动态开点,这样每次修改至多使用 O(log2n)O(\log^2 n) 的空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
int n, q, tot, a[maxn];
struct segment_tree {
int ls, rs, sum;
} tree[maxn * 85];

void seg_modify(int k, int l, int r, int pos, int val) {
if (l == r) {
tree[k].sum = val;
return;
}
int mid = (l + r) >> 1;
if (mid >= pos) {
if (!tree[k].ls) tree[k].ls = ++tot;
seg_modify(tree[k].ls, l, mid, pos, val);
} else {
if (!tree[k].rs) tree[k].rs = ++tot;
seg_modify(tree[k].rs, mid + 1, r, pos, val);
}
tree[k].sum = tree[tree[k].ls].sum + tree[tree[k].rs].sum;
}

int seg_query(int k, int l, int r, int ql, int qr) {
if (!k) return 0;
if (l == ql && r == qr) {
return tree[k].sum;
}
int mid = (l + r) >> 1;
if (mid >= qr) {
return seg_query(tree[k].ls, l, mid, ql, qr);
} else if (mid < ql) {
return seg_query(tree[k].rs, mid + 1, r, ql, qr);
} else {
return seg_query(tree[k].ls, l, mid, ql, mid) + seg_query(tree[k].rs, mid + 1, r, mid + 1, qr);
}
}

void bit_build() {
tot = n;
for (int i = 1; i <= n; i++) {
for (int j = i; j > i - (i & -i); j--) {
seg_modify(i, 1, n, j, 1);
}
}
}

void bit_modify(int pos, int val, int delta) {
for (; pos <= n; pos += pos & -pos) {
seg_modify(pos, 1, n, val, delta);
}
}

int bit_query(int pos, int l, int r) {
int sum = 0;
for (; pos >= 1; pos -= pos & -pos) {
sum += seg_query(pos, 1, n, l, r);
}
return sum;
}

int main() {
scanf("%d %d", &n, &q);
bit_build();
for (int i = 1; i <= n; i++) {
a[i] = i;
}
long long ans = 0;
while (q--) {
int l, r;
scanf("%d %d", &l, &r);
int old1 = bit_query(l - 1, a[l] + 1, n) + bit_query(n, 1, a[l] - 1) - bit_query(l, 1, a[l] - 1);
bit_modify(l, a[l], 0);
int old2 = bit_query(r - 1, a[r] + 1, n) + bit_query(n, 1, a[r] - 1) - bit_query(r, 1, a[r] - 1);
bit_modify(r, a[r], 0);
ans -= old1 + old2;
swap(a[l], a[r]);
bit_modify(l, a[l], 1);
int new1 = bit_query(l - 1, a[l] + 1, n) + bit_query(n, 1, a[l] - 1) - bit_query(l, 1, a[l] - 1);
bit_modify(r, a[r], 1);
int new2 = bit_query(r - 1, a[r] + 1, n) + bit_query(n, 1, a[r] - 1) - bit_query(r, 1, a[r] - 1);
ans += new1 + new2;
printf("%lld\n", ans);
}
return 0;
}