使用到了普通的樹(shù)狀數(shù)組和拓展的樹(shù)狀數(shù)組。
普通的只能單點(diǎn)修改和區(qū)間查詢，利用兩次區(qū)間查詢可以做到單點(diǎn)查詢。如果要區(qū)間修改時(shí)間復(fù)雜度是O(n)。
拓展樹(shù)狀數(shù)組可以區(qū)間修改和區(qū)間查詢，利用兩次區(qū)間操作即可實(shí)現(xiàn)單點(diǎn)操作，但增加了一個(gè)額外的數(shù)組。
題目思路是用一個(gè)普通bit記錄該點(diǎn)是否未排序。一個(gè)拓展bit記錄被排序次數(shù)。

1. 然后模擬插入排序，選取最小點(diǎn)，該點(diǎn)左邊的點(diǎn)被排序次數(shù)都+1（已排序的點(diǎn)可能會(huì)被再次累加，但不影響，原因見(jiàn)第4步）。
2. 該點(diǎn)的被排序次數(shù)+n，n顯然等于該點(diǎn)左邊未排序的點(diǎn)的數(shù)量。
3. 接著更新該點(diǎn)的未排序標(biāo)志。
4. 接著該點(diǎn)將不會(huì)參與后續(xù)排序，所以可以直接累加該點(diǎn)；由于后續(xù)不會(huì)再使用該點(diǎn)的被累加次數(shù)，所以再次執(zhí)行第1步時(shí)，錯(cuò)誤累加該點(diǎn)的被排序次數(shù)不會(huì)對(duì)結(jié)果造成影響。

#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include <utility>
#include <algorithm>

using namespace std;

typedef unsigned long long ull;

int isDebug = 0;

pair<int, int> childs[20]; // hight, index
int unhappy[20 + 1]; // 拓展bit 記錄被排序次數(shù)
int unhappy2[20 + 1];
int counts[20 + 1]; // 普通bit 記錄該點(diǎn)是否未排序

// 普通bit 單點(diǎn)修改 bit[i] += x
void bitAdd(int* bit, int i, int x)
{
    while (i < 21) {
        bit[i] += x;
        i += i & -i;
    }
}

// 拓展bit 區(qū)間修改 bit[i, N] += x
void bitAdd(int* bit1, int* bit2, int i, int x)
{
    int ii = i;
    while (i < 21) {
        bit1[i] += x;
        bit2[i] += x * (ii - 1);
        i += i & -i;
    }
}

// 普通bit 區(qū)間查詢 前i項(xiàng)和 
int bitSum(int* bit, int i)
{
    int s = 0;
    while (i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

// 拓展bit 區(qū)間查詢 前i項(xiàng)和
int bitSum(int* bit1, int* bit2, int i)
{
    int s = 0;
    int ii = i;

    while (i > 0) {
        s += ii * bit1[i] - bit2[i];
        i -= i & -i;
    }

    return s;
}

// 遍歷單點(diǎn)查詢
void debug()
{
    if (!isDebug)
        return;

    int i, last = 0, now = 0;
    for (i = 1; i < 6; i++) {
        now = bitSum(unhappy, unhappy2, i);
        printf("%d\n", now - last);
        last = now;
    }
    printf("\n");
}

int main(void)
{
    freopen("q.txt", "r", stdin);

    int n, N, h, index;
    int last = 0, now = 0, ans = 0;

    scanf("%d", &N);

    for (n = 0; n < N; n++) {
        scanf("%d", &h);
        childs[n].first = h;
        childs[n].second = n + 1;
    }

    sort(childs, childs+n);

    for (n = 1; n < 21; n++)
        bitAdd(counts, n, 1);

    debug();
    for (n = 1; n < 21; n++)
        bitAdd(unhappy, unhappy2, n, 0);
    debug();

    for (n = 0; n < N; n++) {
        index = childs[n].second;

        // 1 o[1, index - 1] += 1
        bitAdd(unhappy, unhappy2, 1, 1);
        debug();
        bitAdd(unhappy, unhappy2, index, -1);
        debug();

        // 2 o[index] += index - n - 1
        int leftCount = bitSum(counts, index-1);
        bitAdd(unhappy, unhappy2, index, leftCount);
        debug();
        bitAdd(unhappy, unhappy2, index + 1, -leftCount);
        debug();

        // 3 計(jì)數(shù)數(shù)組中刪除該節(jié)點(diǎn)
        bitAdd(counts, index, -1);
        // printf("%d %d\n", index, bitSum(unhappy, unhappy2, index) - bitSum(unhappy, unhappy2, index - 1));
        // 4
        index = bitSum(unhappy, unhappy2, index) - bitSum(unhappy, unhappy2, index - 1);
        ans += (1 + index) * index / 2;
    }

    printf("%d\n", ans);

    return 0;
}