2014-07-06

UVa 11990 - ``Dynamic'' Inversion

1. Problem
2. Input
3. Output
4. Sample Input
5. Output for the Sample Input
6. Explanation
7. Solution

Problem

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). The size of input file does not exceed 5MB.

Output

For each removal, output the number of inversion pairs before it.

Sample Input

Output for the Sample Input

Explanation

(1,5,3,4,2)->(1,3,4,2)->(3,4,2)->(3,2)->(3)

Solution

題目描述：

找尋一維數列的逆序對總數，每一次詢問請輸出當時的逆序對個數，隨後將該數字從數列中移除。

題目解法：

一開始可以利用傳統的 D&C 或者是線段樹之類的區間查詢來完成全部的逆序對總數。

隨後要移除某個特定的數字時，要查找該數字前面有多少比它大的數字，以及後面有多少比它小的數字。也就是說，找尋前綴大於某個數字的個數，和找尋後綴小於某個數字的個數，算出有多少對逆序對減少。

這裡使用類似歸併樹的做法，類似合併排序，將會切分成數個區間做排序。並且在每一個區間中會建立一棵離散化後的 binary indexed tree，如果一來記憶體可以在 O(n log n) 解決。

由於我們只需要前綴和後綴的操作，所以說是線段樹可能還有所不及。

每次將前綴拆分成線段樹的數個區間，利用 binary indexed tree，查找當前有多少小於該數字 x 數字被刪除，得到有多少小於 x 的數字還存在 … 之後就可以得到需要的個數。

詳見代碼。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
#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 ret = 0;
    while(x) {
        ret += BIT[x];
        x -= x&(-x); 
    } 
    return ret;
} 
void buildST(int k, 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(k<<1, l, m, dep+1);
    buildST(k<<1|1, m+1, r, dep+1);
    sort(ST[dep] + l, ST[dep] + r+1);
}
void queryPrefix(int k, 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 - l);
        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(k<<1, l, m, dep+1, x, y, val);
    if(y > m)
        queryPrefix(k<<1|1, m+1, r, dep+1, x, y, val);
}
void querySuffix(int k, 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 - l);
        invPair -= (pos - l) - pre;
        return ;
    }
    if(l >= r)	return ;
    int m = (l + r)/2;
    if(x <= m)
        querySuffix(k<<1, l, m, dep+1, x, y, val);
    if(y > m)
        querySuffix(k<<1|1, m+1, r, dep+1, x, y, val);
}
void update(int k, 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(k<<1, l, m, dep+1, x, val);
    else
        update(k<<1|1, m+1, r, dep+1, x, val);
    int pos = lower_bound(ST[dep] + l, 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", &N, &M) == 2) {
        invPair = 0;
        for(int i = 1; i <= N; i++)
            BIT[0][i] = 0;
        for(int i = 1; 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, 1, N, 1);
        
        while(M--) {
            scanf("%d", &DEL);
            printf("%lld\n", invPair);
            queryPrefix(1, 1, N, 1, 1, MP[DEL] - 1, DEL);
            querySuffix(1, 1, N, 1, MP[DEL] + 1, N, DEL);
            update(1, 1, N, 1, MP[DEL], DEL);
        }
    }
    return 0;
}
/*
5 4
1
5
3
4
2
5
*/

Morris' Blog