poj2299 离散化树状数组求逆序对

佚名 5年前 (2019-04-25) 随笔 1734人围观抢沙发百度已收录

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>//poj 2299  题意 输入一个数组，输出冒泡排序 （升序）需要的交换次数
//题解   离散化  树状数组求逆序对
//离散化  将输入数字变成他们大小的顺序 例如： 9 1 0 5 4 变成 5 2 1 4 3
//用lower_bound  或者  结构体就可以实现离散化
//遍历 每个数的移动次数为逆序对的个数  可以用当前的总个数减去比当前数小的数字数（也就是getsum(a[i])）得到
// 也可以用 归并排序 
#define mem0(a) memset(a, 0, sizeof(a))
#define lowbit(x) (x&(-x))
#define ll long long
const int MA = 5e5+100;
int a[MA], b[MA],c[MA],d[MA],n,m;
using namespace std;
struct node{
    int pos,val;
}p[MA];
bool cmp(const node&aa,const node&bb){//not very clear
    return aa.val < bb.val;
}
void add(int k){
    for( ; k <= n; c[k] += 1, k += lowbit(k));
}
int getsum(int k){
    int ret = 0;
    for(; k > 0 ; ret += c[k], k -= lowbit(k));
    return ret;
}
int main(){    
    while(scanf("%d", &n), n){
        mem0(c);
        ll ans = 0;
        /*for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
            b[i] = a[i];
        }
        sort(a+1, a+n+1);
        for(int i = 1; i <= n; i++)
            b[i] = lower_bound(a+1, a+n+1, b[i])-a;
        for(int i = 1; i <= n; i++)
            add(b[i]), ans += i-getsum(b[i]);
        printf("%lld\n", ans);
        */
        for(int i = 1; i <= n; i++) {
            scanf("%d", &p[i].val) ,p[i].pos = i;
        }
        sort(p+1, p+n+1, cmp);
         // for(int i = 1; i <= n; i++) printf(" %d ", p[i].pos);printf("\n");
          //for(int i = 1; i <= n; i++) printf(" %d ", p[i].val);printf("\n");
        for(int i = 1; i <= n; i++) a[p[i].pos] = i;
          //for(int i = 1; i <= n; i++) printf(" %d ", a[i]);printf("\n");
        
        for(int i = 1; i <= n; i++)
        {
            add(a[i]);
            ans += a[i]-getsum(a[i]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}
/*
Sample Input
5
9
1
0
5
4
3
1
2
3
0
Sample Output
6
0
*/