Løsning til opgave B, NCPC 2011, Lambdabamserne

nemB.cpp

#include<cstdio>
#define MAX_N 100050

long long a[MAX_N], aa[MAX_N], p[MAX_N], c[MAX_N];
int N;


inline long long phi(long long n) { return n & (-n); }

void add(long long* arr, long long p, long long c) {
	while(p<N) { arr[p] += c; p += phi(p); }
}

long long get(long long* arr, long long n) {
	long long sum = 0;
	while(n>0) { sum += arr[n]; n -= phi(n); }
	return sum;
}


int main() {
	scanf("%d", &N);
	int k;
	for(int i=1;i<=N;i++) {
		scanf("%d", &k);
		p[N+1-i] = k;
	}
	for(int t=1;t<=N;t++) {
		c[t] = get(a,p[t]-1);
		add(a,p[t],1);
	}
	long long sum = 0;
	for(int t=1;t<=N;t++) {
		sum += get(aa, p[t]-1);
		add(aa,p[t],c[t]);
	}
	printf("%lld\n", sum);
	return 0;
}