1215. 小朋友排队（权值树状数组求逆序数）

题目：

?1215. 小朋友排队 - AcWing题库

思路：权值树状数组?

1.权值树状数组的模板与树状数组一样没有变化，但树状数组tr[]中存储的内容以及add和query的含义发生了变化。

2.tr[]~? 树状数组：存储的是区间和；权值树状数组：存储出现次数。

3.add(x,v)~? 树状数组：是在位置x加上v；权值树状数组：x出现的次数加1

4.query(r)~? 树状数组：原数组区间（a[1]，a[r]）的和；权值树状数组：原数组区间（a[1]，a[r])出现次数。

代码：

//加权树状数组
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

typedef long long LL;//防止爆int

const int N = 1000010;

int n;
int h[N], tr[N];
int sum[N];//表示每个数的逆序个数

//树状数组模板

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

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

int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

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

    // 求每个数前面有多少个数比它大
    for (int i = 0; i < n; i ++ )
    {
        sum[i] = query(N - 1) - query(h[i]);//是N-1而非N是因为tr[]下标最大为N-1
        add(h[i], 1);//在h[i]这个位置加1--->在加权树状数组中表示出现次数加1
    }//加权树状数组的query表示的不是区间值的和，而是在此区间有多少个数

    // 每个数后面有多少个数比它小
    memset(tr, 0, sizeof tr);//清空树状数组
    for (int i = n - 1; i >= 0; i -- )
    {
        sum[i] += query(h[i] - 1);
        add(h[i], 1);
    }

    LL res = 0;
    for (int i = 0; i < n; i ++ ) res += (LL)sum[i] * (sum[i] + 1) / 2;

    cout << res << endl;

    return 0;
}