树状数组例题_求逆序数（poj2299）

传送门：POJ-2299

离散化+树状数组。

我们假设一个数组A[n],当A[n]=0时表示数字n在序列中没有出现过，A[n]=1表示数字n在序列中出现过。A对应的树状数组为c[n],则c[n]对应维护的是数组A[n]的内容，即树状数组c可用于求A中某个区间的值的和。

树状数组的插入函数(假设为 void insert(int i,int x) )的含义：在求逆序数这个问题中，我们的插入函数通常使用为insert( i , 1 )，即将数组A[i]的值加1 (A数组开始应该初始化为0，所以也可以理解为设置A[ i ]的值为1，即将数字i 加入到序列的意思 )。，同时维护c数组的值。

树状数组中区间求和函数(假设函数定义为： int sun(int i ) )的含义：该函数的作用是用于求序列中小于等于数字 i 的元素的个数。这个是显而易见的，因为树状数组c 维护的是数组A的值，则该求和函数即是用于求下标小于等于 i 的数组A的和，而数组A中元素的值要么是0要么是1，所以最后求出来的就是小于等于i的元素的个数。

所以要求序列中比元素a大的数的个数，可以用i – sum(a)即可( i 表示此时序列中元素的个数)。

所以主要思路就是：1.把数据离散化，让数据相互之间更加接近，而不是离散的，2.用树状数组的标准操作来累加求逆序数。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
#define inff 1LL<<60
#define mem(x)	memset(x,0,sizeof(x))
#define LL long long

#define maxn 500100
struct line
{
	int num,pos;
}s[maxn];

int a[maxn],c[maxn];

bool cmp(line a,line b){
	return a.num<b.num;
}

int lowbit(int x){
	return x&(-x);
}

int sum(int x){
	int t=0;
	for(;x>0;t+=c[x],x-=lowbit(x));
	return t;
}

void update(int x){
	for(;x<maxn;c[x]++,x+=lowbit(x));
}

int main(int argc, char const *argv[])
{
	int k;
	while(cin>>k&&k){
		mem(a);mem(c);
		for(int i=1;i<=k;i++){
			cin>>s[i].num;
			s[i].pos=i;
		}
		sort(s+1,s+k+1,cmp);
		for(int i=1;i<=k;i++){
			a[s[i].pos]=i;//把数据离散化
		}
		LL ans=0;
		for(int i=1;i<=k;i++){
			ans+=(a[i]-1)-sum(a[i]);
			update(a[i]);
		}
		cout<<ans<<endl;
	}
	return 0;
}