CH 4201 楼兰图腾（算法竞赛进阶指南， 树状数组）

算法竞赛进阶指南，205页，树状数组
本题要点：
1、利用树状数组求逆序数， 顺序数：
以求 “V” 子图腾为例子， Right[i]表示 a[i] 的后面有几个数比它大， Left[i]表示a[i]前面有几个数比它大
a） 倒叙扫描数组a，利用树状数组去除每个a[i] 后边有几个数比它大， 记为 Right[i]
b） 顺序扫描数组a，利用树状数组去除每个a[i] 前面边有几个数比它大， 记为 Left[i]
答案就是 sum{Right[i] * Left[i]}, 1 <= i <= n

#include <cstdio>
#include <cstring>
#include <iostream>
#define lowbit(i) ((i)&(-i))
using namespace std;
const int MaxN = 200010;
long long a[MaxN], c[MaxN], Left[MaxN], Right[MaxN];
// Right[i]表示 a[i] 的后面有几个数比它大， Left[i]表示a[i]前面有几个数比它大
int n;long long getSum(int x)
{
    long long sum = 0;for(int i = x; i > 0; i -= lowbit(i)){
    sum += c[i];}return sum;
}void update(int x, long long v)
{
    for(int i = x; i <= n; i += lowbit(i)){
    c[i] += v;}
}void solve()
{
    memset(c, 0, sizeof c);for(int i = n; i; --i){
    Right[i] = getSum(n) - getSum(a[i]);update(a[i], 1);}memset(c, 0, sizeof c);for(int i = 1; i <= n; ++i){
    Left[i] = getSum(n) - getSum(a[i]);update(a[i], 1);}long long ans = 0;for(int i = 1; i <= n; ++i){
    ans += Left[i] * Right[i];}printf("%lld", ans);memset(c, 0, sizeof c);for(int i = n; i; --i){
    Right[i] = getSum(a[i] - 1);			//在a[i]后面比a[i]小的update(a[i], 1);}memset(c, 0, sizeof c);for(int i = 1; i <= n; ++i){
    Left[i] = getSum(a[i] - 1);		//在a[i]前面比a[i]小的update(a[i], 1);}ans = 0;for(int i = 1; i <= n; ++i){
    ans += Left[i] * Right[i];}printf(" %lld\n", ans);
}int main()
{
    scanf("%d", &n);for(int i = 1; i <= n; ++i){
    scanf("%lld", &a[i]);}solve();return 0;
}/* 5 1 5 3 2 4 *//* 3 4 */