http://poj.org/problem?id=2299
http://blog.csdn.net/suwei19870312/article/details/5293694
#include <cstdio>
#include<algorithm>
#include <stdlib.h>
#include<string.h>
#define maxn 500005
using namespace std;
struct Node
{
int val,id;
}arr[maxn];
int aa[maxn],c[maxn],n;
int sum(int x)
{
int res=0;
while(x>0)
{
res+=c[x];
x-=x&(-x);
}
return res;
}
void add(int x,int d)
{
while(x<=n)
{
c[x]+=d;
x+=x&(-x);
}
}
int cmp(const void *a,const void *b)
{
return (*(Node *)a).val-(*(Node *)b).val;
}
int main()
{
long long ans;
while(scanf("%d",&n)!=EOF,n)
{
ans=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&arr[i].val);
arr[i].id=i;
}
qsort(arr+1,n,sizeof(Node),cmp);
for(int i=1;i<=n;i++)
aa[arr[i].id]=i;
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)
{
add(aa[i],1);
ans+=i-sum(aa[i]);
}
printf("%lld\n",ans);
}
}
非离散化
#include <cstdio>
#include<algorithm>
#include <stdlib.h>
#include<string.h>
#define maxn 500005
using namespace std;
int arr[maxn],c[maxn],n;
int sum(int x)
{
int res=0;
while(x>0)
{
res+=c[x];
x-=x&(-x);
}
return res;
}
void add(int x,int d)
{
while(x<maxn)
{
c[x]+=d;
x+=x&(-x);
}
}
int main()
{
long long ans;
while(scanf("%d",&n)!=EOF,n)
{
ans=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
arr[i]++;
}
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)
{
add(arr[i],1);
ans+=i-sum(arr[i]);
}
printf("%lld\n",ans);
}
}
