树状数组

作用：
1.快速求前缀和$O(log~n~)$
2.修改某一个数$O(log~n~)$
(折中)

基于二进制

第一个区间的长度是$x$二进制中最后一个$1$对应的次幂
第二个区间的长度是${x-2} ^ {i1} $二进制中最后一个$1$对应的次幂
以此类推…即 $(L,R]$的长度是R的二进制表示的最后一个$1$对应的次幂

这里需要引入一个lowbit()函数：lobit(x) = x & -x
利用这个函数可以求出$x$的二进制表示的最后一个$1$对应的次幂。

则$(L , R]$可以表示为$[R - lowbit[R] + 1 , R]$，所以我们可以用$C[R]$表示该区间的总合

$C[x] = a[x - lowbit(x) + 1 , x]$ ，即以$x$为右端点的长度是$lowbit(x)$的区间内所有数的和

1. 通过父节点找子节点：
   $x$是父节点，先将$x$减去$1$，x的儿子的个数就是末尾1的个数，然后依次找出儿子。
   $C[x] = a[x] + C[x-1] + C[x-1-lowbit(x-1)] + C[x-1-lowbit(x-1)-lowbit(x-1-lowbit(x-1))]…$

2. 子节点找父节点（对应修改操作)
   该操作直接影响到的点是唯一的！
   $P = x + lowbit(x)$

因此树状数组的修改操作如下：

//如果对a[x]进行修改
for(int i = x ; i <= n ; i += lowbit(i)) tr[i] += c;

//查询a[1~x]的和
for(int i = x ; i ; i -= lowbit[i]) res += c[i]

#include <iostream>
#include <cstring>

using namespace std;

const int N = 200010;

int n;
int Greater[N] , lower[N];
int a[N] , tr[N];

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

void add(int x , int c)//为第x个数加上c，这里为了表示是否出现，所以加的是1
{
    for(int i = x ; i <= n ; i += lowbit(i)) tr[i] += c; 
}

//求1~x的和，tr[x]存储的是区间[x−lowbit(x)+1,x]出现的数的次数，题目说y1到yn是1到n的排列，所以这个sum是用来求1~x中出现的数的个数
int sum(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 = 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);//n~y+1之间已出现的数的个数
        lower[i] = sum(y - 1);//1~y-1中已出现的数的个数
        add(y , 1);//记录y这个数已经出现了
    }

    typedef long long LL;
    memset(tr , 0 , sizeof tr);
    LL res1 = 0 , res2 = 0;
     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" , res1 , res2);

    return 0;
}