Inversion

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1051 Accepted Submission(s): 307

Problem Description

You have a sequence

Input

There are multiple test cases. The first line of input contains an integer

Output

For each test case, output the minimum number of inversions.

Sample Input

   2 3 1 1 2 3 4 2 4 1 3 2  

Sample Output

0 1

Source

BestCoder Round #58 (div.2)

思路：

这个题有点棘手，还没有A出来。题意就是，在一段数字序列中剔除掉某个连续序列，求其中最小的一个逆序数。郑燏辉学长说，在此之前推荐可以先看看怎么用树状数组求逆序数，对于这道题可以用两个树状数组来求解，一个树状数组维护剔除序列前面的数的逆序数，另一个用于维护剔除序列后面的逆序数。推荐传送门

有人说，这道题把序列分成三部分 a b c b为去掉的部分，最小逆序数就是整个的逆序数 - a中数>b中数的对数 - b中逆序数 - b中数>c中数的对数，维护时每次去掉一个再加上一个，开线段树就可以了。还不是很懂逆序数的姿势，所以先贴上别人的代码吧，这题有待研究...

代码：

#include<cstdio>  
#include<cstdlib>  
#include<cstring>  
#include<iostream>  
#include<algorithm>  
#include<vector>  
using namespace std;  
typedef long long LL;  
#define lson l,mid,x<<1  
#define rson mid+1,r,x<<1|1  
#define root 0,n+1,1  
const int maxn = 100005;  
  
typedef struct SegTree{  
    int t[maxn*4];  
    void clear(int l,int r,int x) {  
        t[x] = 0;  
        if (l == r) return;  
        int mid = (l + r) / 2;  
        clear(lson);  
        clear(rson);  
    }  
    void update(int p, int add, int l, int r, int x) {  
        if (l == r&&l == p) {  
            t[x] += add;  
            return;  
        }  
        int mid = (l + r) / 2;  
        if (p <= mid) update(p, add, lson);  
        else update(p, add, rson);  
        t[x] = t[x << 1] + t[x << 1 | 1];  
    }  
    int get(int L, int R, int l, int r, int x) {  
        if (L == l&&R == r) return t[x];  
        int mid = (l + r) / 2;  
        if (R <= mid) return get(L, R, lson);  
        if (L > mid) return get(L, R, rson);  
        return get(L, mid, lson) + get(mid + 1, R, rson);  
    }  
}SegTree;  
SegTree A, C, T;  
int n, m, a[maxn];  
int main() {  
    int t;  
    cin >> t;  
    LL ret, tmp;  
    while (t--) {  
        ret = tmp = 0;  
        cin >> n>> m;  
        A.clear(root);C.clear(root);T.clear(root);  
        for (int i = 1;i <= n;i++) {  
            scanf("%d", &a[i]);  
            ret += T.get(a[i] + 1, n + 1, root);//求比现在这个数大的  
            T.update(a[i], 1, root);//加入这个数  
        }  
        T.clear(root);  
        for (int i = 1;i <= m;i++) {  
            tmp += T.get(a[i] + 1, n + 1, root);//求B内部逆序  
            T.update(a[i], 1, root);  
        }  
        for (int i = m + 1;i <= n;i++) {  
            C.update(a[i], 1, root);//求B大于C部分  
            tmp += T.get(a[i] + 1, n + 1, root);  
        }  
        LL Max = tmp;  
        for (int i = 1;i <= n - m;i++) {  
            int mm = a[i], tt = a[i + m];  
            tmp -= A.get(mm + 1, n + 1, root);//a中大于m的  
            tmp -= C.get(0, mm - 1, root);  
  
            A.update(mm, 1, root);  
  
            tmp += A.get(tt + 1, n + 1, root);  
            tmp += C.get(0, tt - 1, root);  
  
            Max = max(tmp, Max);  
  
            C.update(tt, -1, root);   
        }  
        printf("%lld\n", ret - Max);  
    }  
    return 0;  
}

HDOJ 5497 Inversion（两个树状数组）（待解决）

Inversion