1009 Triple Inversions

Statement

Metadata

作者: CAO, Peng
单位: Google
代码长度限制: 16 KB
时间限制: 300 ms
内存限制: 64 MB

Given a list of $N$ integers $A_1$ , $A_2$ , $A_3$ ,… $A_N$ , there's a famous problem to count the number of inversions in it. An inversion is defined as a piar of indices $i < j$ such that $A_i > A_j$ .

Now we have a new challenging problem. You are supposed to count the number of triple inversions in it. As you may guess, a triple inversion is defined as a triple of indices $i < j < k$ such that $A_i > A_j > A_k$ . For example, in the list { 5, 1, 4, 3, 2 } there are 4 triple inversions, namely (5,4,3), (5,4,2), (5,3,2) and (4,3,2). To simplify the problem, the list $A$ is given as a permutation of integers from 1 to $N$ .

Input Specification

Each input file contains one test case. For each case, the first line gives a positive integer $N$ in [ $3, 10^5$ ]. The second line contains a permutation of integers from 1 to $N$ and each of the integer is separated by a single space.

Output Specification

For each case, print in a line the number of triple inversions in the list.

Sample Input

22
1 2 3 4 5 16 6 7 8 9 10 19 11 12 14 15 17 18 21 22 20 13

Sample Output

Solution

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
int n, a[N];
struct BIT {
    ll a[N];
    void init() {
        memset(a, 0, sizeof a);
    }
    void update(int x, ll v) {
        for (; x < N; x += x & -x) a[x] += v;
    }
    ll query(int x) {
        ll res = 0;
        for (; x > 0; x -= x & -x) res += a[x];
        return res;
    }
    ll query(int l, int r) {
        if (l > r)
            return 0;
        return query(r) - query(l - 1);
    }
} bit[2];

int main() {
    while (scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; ++i) scanf("%d", a + i);
        ll res = 0;
        for (int i = 1; i <= n; ++i) {
            bit[0].update(a[i], 1);
            bit[1].update(a[i], bit[0].query(a[i] + 1, n));
            res += bit[1].query(a[i] + 1, n);
        }
        printf("%lld\n", res);
    }
    return 0;
}

Last update: May 4, 2022