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