树状数组 poj2299

树状数组 poj2299"/>

树状数组 poj2299

题目大意就是要你求给定数组的逆序对，逆序对的个数即为交换的次数。

我们先进性离散化，在将数一个个放到树状数组中去。我们更新操作是将从大区间向小区间更新，更新完之后立马查询当前的大区间（即为前面有多少个数大于当前数）

#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <stdio.h>
#include <ctype.h>
#include <bitset>
#define  LL long long
#define  ULL unsigned long long
#define mod 10007
#define INF 0x7ffffff
#define mem(a,b) memset(a,b,sizeof(a))
#define MODD(a,b) (((a%b)+b)%b)
using namespace std;
const int maxn = 3e6 + 5;
int a[maxn],sum[maxn],n;
vector<int> V;
int getId(int x){return lower_bound(V.begin(),V.end(),x) - V.begin() + 1;}
int lowbit(int x){return x&(-x);}
void upDate(int x,int t)
{while(x > 0){sum[x]+=t;x-=lowbit(x);}return ;
}
LL query(int x)
{LL ans = 0;while(x <= n){ans+=sum[x];x += lowbit(x);}return ans;
}
int main()
{while(~scanf("%d",&n) && n){mem(sum,0);V.clear();for(int i = 1; i <= n; i++) {scanf("%d",&a[i]);V.push_back(a[i]);}sort(V.begin(),V.end());V.erase(unique(V.begin(),V.end()),V.end());LL ans = 0;for(int i = 1; i <= n; i++){upDate(getId(a[i]),1);ans += query(getId(a[i]));}printf("%lld\n",ans - n);}return 0;
}