[training day15] simple calculation [tree array] [mathematics]

Ideas ：

We can count the same , Then subtract it

$code$

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;

const long long MAXN = 1e5 + 10;

long long n;
long long a[MAXN], l[MAXN], r[MAXN], l1[MAXN], r1[MAXN];
long long cl[MAXN], cr[MAXN];
long long tot, k[MAXN];

long long lowbit(long long x) {
     return x & -x; }

void add_l(long long x) {
    
	for(; x <= MAXN - 10; x += lowbit(x)) cl[x] ++;
}

long long query_l(long long x) {
    
	long long ans = 0;
	for(; x; x -= lowbit(x)) ans += cl[x];
	return ans;
}

void add_r(long long x) {
    
	for(; x <= MAXN - 10; x += lowbit(x)) cr[x] ++;
}

long long query_r(long long x) {
    
	long long ans = 0;
	for(; x; x -= lowbit(x)) ans += cr[x];
	return ans;
}

int main() {
    
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
	scanf("%lld", &n);
	for(long long i = 1; i <= n; i ++) scanf("%lld", &a[i]), k[i] = a[i];
	sort(k + 1, k + 1 + n);
	int tot = unique(k + 1, k + 1 + n) - k - 1;
	for(long long i = 1; i <= n; i ++) a[i] = lower_bound(k + 1, k + 1 + tot, a[i]) - k;
	long long s1 = 0, s2 = 0;
	for(long long i = 1; i <= n; i ++) {
    
		add_l(a[i]);
		s1 += query_l(a[i] - 1);
		l[i] = query_l(a[i] - 1);
		l1[i] = query_l(MAXN) - query_l(a[i]);
	}
	for(long long i = n; i >= 1; i --) {
    
		add_r(a[i]);
		s2 += query_r(a[i] - 1);
		r[i] = query_r(MAXN) - query_r(a[i]);
		r1[i] = query_r(a[i] - 1);
	}
	long long s3 = 0;
	for(long long i = 1; i <= n; i ++) s3 += l[i] * r1[i] + r[i] * l1[i] + l1[i] * l[i] + r[i] * r1[i];
	printf("%lld", s1 * s2 - s3);
 	return 0;
}
/* a b c d 1 4 4 3 1 4 4 2 1 3 3 2 */

/* 1 4 1 3 1 2 3 2 4 2 4 3 */