树状数组求逆序对 线段树感觉大材小用了
C++ 代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e5+10;
int a[maxn],b[maxn],c[maxn];
int n;
void update(int x){for(;x<=n;x+=-x&x)c[x]++;}
int sum(int x)
{
int ans = 0;
for(;x>0;x-=-x&x)ans+=c[x];
return ans;
}
signed main(int argc, char const *argv[])
{
while(~scanf("%lld",&n)&&n)
{
int ans = 0; memset(c,0,sizeof(c));
for(int i = 1; i <= n; ++i) scanf("%lld",&a[i]),b[i]=a[i];
sort(a+1,a+1+n);
for(int i = 1; i <= n; ++i) b[i]=lower_bound(a+1,a+1+n,b[i])-a;
for(int i = n; i; --i)
{
update(b[i]);
ans += sum(b[i]-1);
}
printf("%lld\n",ans);
}
return 0;
}