POJ 2299 树状数组入门 离散化入门

树状数组入门 离散化入门"/>

POJ 2299 树状数组入门 离散化入门

 思路见注释，套两个模板就好，没什么技巧

//理解了快速排序的时间复杂度 不难发现这道题是一个
//纯树状数组 + 逆序对 直接套模板就好了
//树状数组每个结点存放的是小于等于该结点的value
//逆序对公式：逆序对=大于该value的个数
//因为树状数组的n取决于序列的最大值
//所以套个离散化模板就好了
//离散化模板为不重复模板
//lowbit的含义是计算二进制数中从右数第一个1的位置
//例如6(0110)->2
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define Lowbit(x) (x&(-x))
using namespace std;
const int maxn=5e5+10;
struct node {int val;int pos;
} p[maxn];
int n,bit[maxn],a[maxn];
bool cmp(const node& a,const node& b) {return a.val<b.val;
}
void update(int x) {while(x<=n) {bit[x]++;//x+=Lowbit(x);//向上更新x+=(__builtin_ctz(x)+1);//__builtin_ctz为glibc库中的函数，意思是取出二进制数从右数第一个1后面的0的个数}
}
int sum(int x) {int ans=0;while(x>0) {ans+=bit[x];//x-=Lowbit(x);x-=(__builtin_ctz(x)+1);}return ans;
}
int main(void){freopen("E:\\input.txt","r",stdin);ios::sync_with_stdio(false);while(cin>>n&&n){for(int i=1;i<=n;i++){cin>>p[i].val;p[i].pos=i;}sort(p+1,p+n+1,cmp);for(int i=1;i<=n;i++)a[p[i].pos]=i;long long ans=0;memset(bit,0,sizeof(int)*(n+5));for(int i=1;i<=n;i++){update(a[i]);ans+=i-sum(a[i]);}cout<<ans<<endl;}return 0;
}