树状数组

www.bilibili.com

int n;
int a[N];    // 原数组, a[1, n]
int c[N];    // 树状数组, c[1, n]

// c[i]的区间长度
int lowbit(int x) {
  return x & (-x);
}

// 点更新, a[i]加上 x, 更新 c[]
void add(int i, int x) {
  // 更新所有的祖先
  for( ; i <= n; i += lowbit(i))
    c[i] += x;
}

// 前缀和, a[1] + a[2] + ... + a[i]
int sum(int i) {
  int res = 0;
  for( ; i > 0; i -= lowbit(i))
      res += c[i];
  return res;
}

// 区间和, a[i] + a[i + 1] + ... a[j]
int sum(int i, int j) {
  return sum(j) - sum(i - 1);
}

AcWing 241. 楼兰图腾

AcWing 241. 楼兰图腾 - AcWing

#include 
<cstring>
#include 
<iostream>
#include 
<algorithm>

using namespace std;
using LL = long long;

const int N = 2e5 + 10;

int n;
int a[N];
int tr[N];
// Lower[i]表示左边比第 i个位置小的数的个数
// Greater[i]表示左边比第 i个位置大的数的个数
int Greater[N], Lower[N];

// 返回 x最后一位 1及其后面的 0所表示的数 
int lowbit(int x) {
    return x & -x;
}

void add(int i, int x) {
    for( ; i <= n; i += lowbit(i))
        tr[i] += x;
}

int sum(int i) {
    int s = 0;
    for( ; i > 0; i -= lowbit(i))
        s += tr[i];
    return s;
}

int sum(int i, int j) {
    return sum(j) - sum(i - 1);
}

int main() {
    cin >> n;

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

    LL res1 = 0, res2 = 0;

    // 从左往右, 统计的是比当前值 大/小 的总数 
    for(int i = 1; i <= n; i++) {
        int x = a[i];

        // 将 x的值看成 tr数组的下标
        // 看目前 也就是当前数的左边的数 的值在 [x + 1, n], 也就是大于 x一共有多少个数
        Greater[i] = sum(x + 1, n);
        Lower[i] = sum(x - 1);

        /*
            求得位置 i前面小于 a[i]数字的个数 Lower[i]以后
            已知一共有 a[i] - 1个数小于 a[i]
            剩下的 a[i] - 1 - Lower[i]个数一定就在位置 i的右边了
        */
        res1 += (LL)Greater[i] * (n - x - Greater[i]);
        res2 += (LL)Lower[i] * (x - Lower[i] - 1);

        // 值为 x的个数 +1, 动态维护 树状数组, 树状数组实际上维护的是 01即 个数数组 
        add(x, 1);
    }

    /*
        memset(tr, 0, sizeof tr);

        for(int i = n; i > 0; i--) {
            int x = a[i];
            res1 += Greater[i] * (LL)sum(x + 1, n);
            res2 += Lower[i] * (LL)(sum(x - 1));

            add(x, 1); 
        } 
    */

    printf("%lld %lld\n", res1, res2);

    return 0;
}