Triple Inversions

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]. 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:

8

 1 #include<bits/stdc++.h>
 2 #include<ext/pb_ds/assoc_container.hpp>
 3 using namespace std;
 4 using namespace __gnu_pbds;
 5 int main()
 6 {
 7 //    freopen("data.txt","r",stdin);
 8     tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> tr;
 9     long long n,x,s=0;
10     long long r,b;
11     scanf("%lld",&n);
12     for(long long i=1;i<=n;i++)
13     {
14         scanf("%lld",&x);
15         tr.insert(x);
16         r=tr.size()-tr.order_of_key(x)-1;
17         b=r-i+x;
18         s=s+r*b;
19     }
20     printf("%lld",s);
21     return 0;
22 }

Triple Inversions

原文：https://www.cnblogs.com/SkystarX/p/12285805.html