POJ 2299（Ultra-QuickSort）树状数组解逆序数

题目分析：这个题目就是用一个结构体数组，把每个数的值记录下来，还有他初始在数组里的位置，然后进行从小到大排序。

这样就够成了条件1）先插入的必定是值比前面大的！然后每次进行求和，2）只要初始位置也就是坐标轴上的X在我前面的个数就是当前这个数构成逆序的对数。

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;

inline int lowbit(int x){
	return x&(-x);
}
long long c[500001];
long long  sum;
struct node{
	int num,sert;
}t[500001];

long long getsum(int n){
	int ans=0;
	while(n>0){
		ans+=c[n];
		n-=lowbit(n);
	}
	return ans;
}

int modify(int num,int count){
	while(num<500001){
		c[num]+=count;
		num+=lowbit(num);
	}
	return 0;
}

int cmp(struct node a,struct node b){
	return a.num>b.num;
}

int main(){
	int i,N;
	while(scanf("%d",&N),N){
		sum=0;
		memset(c,0,sizeof(c));
		for(i=1;i<=N;i++){
			cin>>t[i].num;
			t[i].sert=i;
		}	
		sort(t+1,t+1+N,cmp);
		for(i=1;i<=N;i++){	
			sum+=getsum(t[i].sert);
                       //先求和在修改，这样因为第一个插入的肯定               
                       //为0，符号实际意义
			modify(t[i].sert,1);
                       //修改的时候只需要把该位置改为1，也就是代表个数
		}
		cout<<sum<<endl;
	}
	return 0;
}