AcWing 241 楼兰图腾

题目传送门

树状数组主要解决的是

• 1、a[x] += c (单点修改)
• 2、求a[L ~ R] (前缀和)

#include 
using namespace std;
const int N = 2000010;
typedef long long LL;

int n;
// t[i]表示树状数组i结点覆盖的范围和
int a[N], t[N];

// 可以理解为前缀和
// l1[i]表示左边比第i个位置小的数的个数
// g1[i]表示左边比第i个位置大的数的个数
int l1[N], g1[N];

// 可以理解为后缀和
// l2[i]表示右边比第i个位置小的数的个数
// g2[i]表示右边比第i个位置大的数的个数
int l2[N], g2[N];

//返回非负整数x在二进制表示下最低位1及其后面的0构成的数值
int lowbit(int x) {
    return x & -x;
}
//将序列中第x个数加上k
void add(int x, int k) {
    for (int i = x; i <= n; i += lowbit(i)) t[i] += k;
}
//查询序列前x个数的和
int sum(int x) {
    int sum = 0;
    for (int i = x; i; i -= lowbit(i)) sum += t[i];
    return sum;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    //从左向右，依次统计每个位置左边比第i个数y小的数的个数、以及大的数的个数
    for (int i = 1; i <= n; i++) {
        int y = a[i];
        // 1 ~ y-1之间有多少个数
        l1[i] = sum(y - 1);
        // y+1 ~ n有多少个数
        g1[i] = sum(n) - sum(y);
        //将y加入树状数组，即数字y出现1次
        add(y, 1);
    }

    //清空树状数组，从右往左统计每个位置右边比第i个数y小的数的个数、以及大的数的个数
    memset(t, 0, sizeof t);

    //从右向左
    for (int i = n; i >= 1; i--) {
        int y = a[i];
        l2[i] = sum(y - 1);
        g2[i] = sum(n) - sum(y);
        add(y, 1);
    }

    //用乘法原理统计结果
    LL resA = 0, resV = 0;
    for (int i = 1; i <= n; i++) {
        resA += (LL)l1[i] * l2[i];
        resV += (LL)g1[i] * g2[i];
    }
    //输出
    printf("%lld %lld\n", resV, resA);
    return 0;
}