树状数组

重点
1. 树状数组的两种基本操作：查询前缀和，添加一个数并维护前缀和
2. 树状求逆序对

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 200010;
int a[N];
int tr[N], Greater[N], lower[N];
int n;

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

void add(int x, int c) {  //在下标为x处，加上c
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int x) {  //求到下标x处的前缀和
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i++) {
        int y = a[i];
        Greater[i] = sum(n) - sum(y);
        lower[i] = sum(y - 1);
        add(y, 1);
    }
    LL res1 = 0, res2 = 0;
    memset(tr, 0, sizeof(tr));
    for (int i = n; i; i--) {
        int y = a[i];
        res1 += Greater[i] * (LL)(sum(n) - sum(y));
        res2 += lower[i] * (LL)(sum(y - 1));
        add(y, 1);
    }
    printf("%lld %lld\n", res1, res2);
    return 0;
}