求逆序数的模板题
我自己用的是树状数组求得，因为a[i]值最多为999999999，但是最多只有500000个元素，所以需要离散化一下
看网上还有别的算法，感觉都差不多，都是nlogn的算法
1522117110810Ultra-QuickSortAcceptedC++0.3392015-03-26 11:25:11
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const int maxn = 555555;LL array[maxn];LL hash[maxn];int C[maxn];int n;int lowbit(int x){return x & -x;}void add(int x,int d){while(x <= n){C[x] += d;x += lowbit(x);}}int sum(int x){int ret = 0;while(x > 0){ret += C[x];x -= lowbit(x);}return ret;}void get_hash(){for(int i = 0; i < n; i++){LL e = hash[i];int pos = lower_bound(array,array + n,e) – array;//printf("%d ",pos);hash[i] = pos + 1;}}void solve(){LL ans = 0;for(int i = 0; i < n; i++){int e = (int)hash[i];//printf("%d\n",e);ans += (sum(n) – sum(e – 1));//printf("%d %d\n",e,ans);add(e,1);}printf("%lld\n",ans);}int main(){while(scanf("%d",&n) && n){memset(C,0,sizeof(C));for(int i = 0; i < n; i++){scanf("%lld",&array[i]);hash[i] = array[i];}sort(array,array + n);get_hash();solve();}return 0;}
，可就是这样，还是有人，期望过多的温暖。
