维护名次即可（不需要离散化）。
# include <stdio.h>
# include <string.h>
# include <algorithm>
using namespace std;
# define N 500005
typedef long long int LL;
int n;
LL a[N];
int r[N], s[N], c[N];
/***************************************************/
int getsum(int x)
{
int ret = 0;
while (x > 0) ret += c[x], x -= x&(-x);
return ret;
}
void inc(int x)
{
while (x <= n) ++ c[x], x += x&(-x);
}
/***************************************************/
bool cmp(int x, int y)
{
return a[x] > a[y];
}
int main()
{
LL ans;
int i;
while (scanf("%d", &n), n)
{
memset(c+1, 0, sizeof(c[0])*n);
for (i = 0; i < n; ++i)
r[i] = i, scanf("%lld", &a[i]);
sort(r, r+n, cmp);
for (i = 0; i < n; ++i) s[r[i]] = i;
ans = 0;
for (i = 0; i < n; ++i)
ans += getsum(s[i]+1), inc(s[i]+1);
printf("%lld\n", ans);
}
return 0;
}
posted on 2012-09-02 17:53
yajunw 阅读(131)
评论(0) 编辑 收藏 引用