树状数组例题_求逆序数(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;
}

 

喜欢()
评论 (0)
热门搜索
37 文章
3 评论
11 喜欢
Top