Contents

1. 1. 题目：
2. 2. 注意： 树状数组下标要从1开始
3. 3. 分析：
   1. 3.1. 离散化:

题目：

http://poj.org/problem?id=2299

注意： 树状数组下标要从1开始

分析：

例如 ：
pos:1 2 3 4 5
val: 9 1 0 5 4

离散化:

　　将上面的val变为5 2 1 4 3 离散后的数据
　　 　输入的顺序为1 2 3 4 5 reflect数组的下标

sort(node + 1, node + 1 + n, cmp);
val: 0 1 4 5 9
pos: 3 2 5 4 1
val离散成下标1 2 3 4 5
就成了：1的输入顺序是3,2的输入顺序是2,3的输入顺序是5,4的输入顺序是4，5的输入顺序是1
reflect[node[i].pos] = i;
　reflect下标: 1 2 3 4 5
离散后的数据:5 2 1 4 3 (按输入的顺序)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 500005;

struct Node{
    int val;				//储存原始的数据
    int pos;				//储存原始的下标
};

Node node[N];
int n;
int tree[N], reflect[N];		//树状数组，映射数组

bool cmp(const Node &a, const Node &b){

    return a.val < b.val;
}

int lowbit(int x){

    return x & -x;
}

void update(int index, int val){

    while(index <= n){
        tree[index] += val;
        index += lowbit(index);
    }
}

int getsum(int index){

    int sum = 0;
    while(index > 0){
        sum += tree[index];
        index -= lowbit(index);
    }
    return sum;
}

int main(){

    while(scanf("%d", &n) != EOF && n){
        for(int i = 1; i <= n; i++){
            scanf("%d", &node[i].val);
            node[i].pos = i;
        }
        sort(node + 1, node + 1 + n, cmp);//将结构数组里的元素根据val从小到大排序
        for(int i = 1; i <= n; i++){
            reflect[node[i].pos] = i;	  //离散化
        }
        for(int i = 1; i <= n; i++)
            tree[i] = 0;//初始化树状数组
        long long ans = 0;
        for(int i = 1; i <= n; i++){
            update(reflect[i], 1);
            ans += i - getsum(reflect[i]); //i减去小于等于他的个数得出比他大个数
        }
        printf("%lld\n", ans);
    }
    return 0;
}