維護名次即可（不需要離散化）。
#?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 閱讀(152)
評論(0) 編輯 收藏 引用