【刷题】数据结构——树状数组：楼兰图腾

题目链接

二维坐标轴上有n个点，横坐标分别为1~n，需要找出所有满足高低高和低高低的三元组，求这些三元组的数量。

对于高低高：
只需要求每个位置左边有多少数大于它，右边有多少数大于它，两者相乘即可。

初始集合为空，从左往右扫描一遍，对于每个位置i，求出当前集合有多少数大于yi，即区间[yi+1, n]有多少个数，然后将yi加入集合中；
初始集合为空，再从右往左扫描一遍，求出当前集合有多少数大于yi，然后将yi加入集合中。
想要快速求出一个区间有多少个数，每出现一个数在相应位置+1，然后用前缀和即可。例如区间[yi+1, n]就是sum(n) - sum(yi)

低高低同理，求多少个数小于yi，换成区间[0, yi-1]，也就是sum(yi-1)即可。

这边的前缀和和更新就可以用树状数组。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 200005;
int n;
int a[N], t[N];
int big[N], small[N];
long long res1, res2;

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

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

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

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

    for (int i = 0; i < n; i ++ ) {
        big[i] = sum(n) - sum(a[i]);
        small[i] = sum(a[i] - 1);
        add(a[i], 1);
    }
    memset(t, 0, sizeof(t));


    for (int i = n - 1; i >= 0; i -- ) {
        res1 += (long long)big[i] * (sum(n) - sum(a[i]));
        res2 += (long long)small[i] * sum(a[i] - 1);
        add(a[i], 1);
    }
    cout << res1 << " " << res2 << endl;
	return 0;
}