Tokitsukaze and Strange Inequality (Codeforces 1678C)
Tags: Others, data structures

Tokitsukaze has a permutation $$$p$$$ of length $$$n$$$. Recall that a permutation $$$p$$$ of length $$$n$$$ is a sequence $$$p_1, p_2, \ldots, p_n$$$ consisting of $$$n$$$ distinct integers, each of which from $$$1$$$ to $$$n$$$ ($$$1 \leq p_i \leq n$$$).She wants to know how many different indices tuples $$$[a,b,c,d]$$$ ($$$1 \leq a < b < c < d \leq n$$$) in this permutation satisfy the following two inequalities:  $$$p_a < p_c$$$ and $$$p_b > p_d$$$. Note that two tuples $$$[a_1,b_1,c_1,d_1]$$$ and $$$[a_2,b_2,c_2,d_2]$$$ are considered to be different if $$$a_1 \ne a_2$$$ or $$$b_1 \ne b_2$$$ or $$$c_1 \ne c_2$$$ or $$$d_1 \ne d_2$$$.

Input: The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. Each test case consists of two lines.The first line contains a single integer $$$n$$$ ($$$4 \leq n \leq 5000$$$) — the length of permutation $$$p$$$.The second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — the permutation $$$p$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output: For each test case, print a single integer — the number of different $$$[a,b,c,d]$$$ tuples.

Note: In the first test case, there are $$$3$$$ different $$$[a,b,c,d]$$$ tuples.$$$p_1 = 5$$$, $$$p_2 = 3$$$, $$$p_3 = 6$$$, $$$p_4 = 1$$$, where $$$p_1 < p_3$$$ and $$$p_2 > p_4$$$ satisfies the inequality, so one of $$$[a,b,c,d]$$$ tuples is $$$[1,2,3,4]$$$.Similarly, other two tuples are $$$[1,2,3,6]$$$, $$$[2,3,5,6]$$$.

Sample Inputs:
3
6
5 3 6 1 4 2
4
1 2 3 4
10
5 1 6 2 8 3 4 10 9 7

Sample Outputs:
3
0
28

Solution (Python):
from sys import stdin, stdout
input = stdin.readline
if __name__ == '__main__':
    t = int(input().strip())
    for _ in range(t):
        n = int(input().strip())
        a = list(map(int, input().strip().split()))
        ans = 0
        dp = [0 for _ in range(n)]
        for i in range(n - 1, -1, -1):
            cnt = 0
            for j in range(i - 1, -1, -1):
                if a[i] > a[j]:
                    ans += cnt
                cnt += dp[j]
                if a[i] < a[j]:
                    dp[j] += 1
        print(ans)

Solution (Python):
from sys import stdin, stdout
int_in = lambda : int(stdin.readline())
arr_in = lambda : [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for _ in range(rows)]
str_in = lambda : stdin.readline().strip()
out = lambda o: stdout.write('{}\n'.format(o))
arr_out = lambda o: out(' '.join(map(str, o)))
bool_out = lambda o: out('YES' if o else 'NO')
tests = lambda : range(1, int_in() + 1)
case_out = lambda i, o: out('Case #{}: {}'.format(i, o))

def solve(n, p):
    result = 0
    a_less_than_c_cache = [0] * n
    for b in range(n):
        d_less_than_b = 0
        for c in reversed(range(b + 1, n)):
            result += a_less_than_c_cache[c] * d_less_than_b
            if p[b] < p[c]:
                a_less_than_c_cache[c] += 1
            else:
                d_less_than_b += 1
    return result
if __name__ == '__main__':
    for _ in tests():
        out(solve(int_in(), arr_in()))

Solution (Python):
t = int(input())
for x in range(t):
    n = int(input())
    p = list(map(int, input().split()))
    a = [0] * n
    b = [0] * n
    ans = 0
    for i in range(1, n - 2):
        for j in range(n - 2, i, -1):
            if p[i - 1] < p[j]:
                a[j] += 1
            if p[j + 1] < p[i]:
                b[i] += 1
            ans += a[j] * b[i]
    print(ans)