hoj 2275 Number sequence(ツリー配列)
1280 ワード
シーケンスにaiak(iツリー配列を2回使用します.注意:aiは0!!
/*This Code is Submitted by yew1eb for Problem 2275 at 2014-01-13 11:14:55*/
#include <stdio.h>
#include <string.h>
#define MAXA 32768
#define MAXN 50000 + 10
typedef long long LL;
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
inline int lowbit(int x) {return (x&-x);}
void modify(int i, int d) {for(;i<=MAXA; i +=lowbit(i)) c[i] +=d;}
int sum(int i) {int ret = 0; for(;i>0; i-=lowbit(i)) ret+=c[i]; return ret;}
int main()
{
int n, i;
LL ans;
while(scanf("%d",&n)!=EOF) {
memset(c, 0, sizeof c);
for(i=1; i<=n; ++i) {
scanf("%d",&d[i]);
a[i] = sum(d[i]);
modify(d[i]+1, 1);
}
memset(c, 0, sizeof c );
for(i=n; i>0; --i) {
b[i] = sum(d[i]);
modify(d[i]+1, 1);
}
ans = 0;
for(i=1; i<=n; ++i) {
ans += (LL)a[i]*(LL)b[i];
}
printf("%lld
",ans);
}
}