Description
You are given a permutation {1,2,3,. . . ,n}. Remove m of them one by one, and output the number of inversion pairs before each removal. The number of inversion pairs of an array A is the number of ordered pairs (i, j) such that i < j and A[i] > A[j].
Input
The input contains several test cases. The first line of each case contains two integers n and m (1 ≤ n ≤ 200, 000, 1 ≤ m ≤ 100, 000). After that, n lines follow, representing the initial permutation. Then m lines follow, representing the removed integers, in the order of the removals. No integer will be removed twice. The input is terminated by end-of-file (EOF).
Output
For each removal, output the number of inversion pairs before it.
Explanation: (1,5,3,4,2)->(1,3,4,2)->(3,4,2)->(3,2)->(3)
Sample Input
5 4
1
5
3
4
2
5
1
4
2
Sample Output
5
2
2
1
Problem Analysis:
We can see each time remove an item, the number of inversion pairs changed. And we can consider the number of inversion pairs as a two part, the region before removed the item, and another is after it.
So it is better to use segment tree structure to count the number, every time removed, we only need to update counting it one time.
#define MAXN 200005
int N, M, DEL;
int ST[20][MAXN], BIT[20][MAXN];
int MP[MAXN];
long long invPair;void modifySum(int BIT[], int x, int v, int L) {
while (x <= L) {
BIT[x] += v;
x += x & (-x);
}
}int querySUM(int BIT[], int x) {
int res = 0;
while (x) {
res += BIT[x];
x -= x & (-x);
}
return res;
}void buildST(int l, int r, int dep) {
for (int i = l; i <= r; ++i) {
ST[dep][i] = ST[dep - 1][i], BIT[dep][i] = 0;
if (l >= r) return; int m = (l + r) / 2;
buildST(l, m, dep + 1);
buildST(m + 1, r, dep + 1);
sort(ST[dep] + l, ST[dep] + r + 1);
}void queryPrefix(int l, int r, int dep, int x, int y, int val) {
if (x <= l && r <= y) {
int pos = upper_bound(ST[dep] + 1, ST[dep] + r + 1, val) - ST[dep];
int pre = querySUM(BIT[dep] + l - 1, pos - 1);
invPair -= (r - pos + 1) - (querySUM(BIT[dep] + l - 1, r - l + 1) - pre); return;
} if (l >= r) return; int m = (l + r) / 2;
if (x <= m) queryPrefix(l, m, dep + 1, x, y, val);
if (y > m) queryPrefix(m + 1, r, dep + 1, x, y, val);
}void querySuffix(int l, int r, int dep, int x, int y, int val) {
if (x <= l && r <= y) {
int pos = upper_bound(ST[dep] + l, ST[dep] + r + 1, val) - ST[dep];
int pre = querySUM(BIT[dep] + l - 1, pos - 1);
invPair -= (pos - l) - pre;
} if (l >= r) return; int m = (l + r) / 2;
if (x <= m) querySuffix(l, m, dep + 1, x, y, val);
if (y > m) querySuffix(m + 1, r, dep + 1, x, y, val);
}void update(int l, int r, int dep, int x, int val) {
if (l == r) {
modifySUM(BIT[dep] + l - 1, 1, 1, r - l + 1);
return;
} if (l >= r) return; int m = (l + r) / 2;
if (x <= m) update(l, m, dep + 1, x, val);
else update(m + 1, r, dep + 1, x, val); int pos = lower_bound(ST[dep] + 1, ST[dep] + r + 1, val) - ST[dep];
modifySUM(BIT[dep] + l - 1, pos - l + 1, 1, r - l + 1);
}int main() {
while (scanf("%d %d", &M, &N) == 2) {
invPair = 0;
for (int i = 0; i <= N; ++i) BIT[0][i] = 0;
for (int i = 0; i <= N; ++i) {
scanf("%d", &ST[0][i]);
MP[ST[0][i]] = i;
invPair += i - 1 - querySUM(BIT[0], ST[0][i]);
modifySUM(BIT[0], ST[0][i], 1, N);
}
buildST(1, N, 1); while (M--) {
scanf("%d", &DEL);
printf("%lld\n", invPair);
queryPrefix(1, N, 1, 1, MP[DEL] - 1, DEL);
querySuffix(1, N, 1, MP[DEL] + 1, N, DEL);
update(1, N, 1, MP[DEL], DEL);
}
} return 0;
}
time complexity is O(mnlogn)
space complexity is O(nlogn)