Quadruples With a Swap in the Middle

Hard

You are given an array perm of length n that is a permutation of 1 to n. Call indices i < j < k < l a **swapped quadruple** if perm[i] < perm[k] < perm[j] < perm[l]. In other words, the values increase except that the middle pair comes in the wrong order: perm[j] is larger than perm[k]. Return the number of such quadruples. Trying all quadruples is O(n⁴); with n up to 4000 you need O(n²).

Example 1

perm=[2, 4, 3, 5, 1] → 1

The indices (0, 1, 2, 3) work: the values are 2, 4, 3, 5, and indeed 2 < 3 < 4 < 5.

Example 2

perm=[1, 4, 2, 3, 5] → 2

(0, 1, 2, 4) with values 1, 4, 2, 5 and (0, 1, 3, 4) with values 1, 4, 3, 5 both work.

Example 3

perm=[1, 2, 3, 4] → 0

The array is increasing, so the second element of a quadruple is never larger than the third.

Constraints

4 ≤ n ≤ 4000
perm is a permutation of 1 to n

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Binary Indexed Tree Array Dynamic Programming Enumeration Prefix Sum

Similar problems

Shift a Segment to Match Medium The Heaviest Reading Day Hard Merge Neighbouring Piles in Groups Hard Cutting a Berry Cake Hard Ferry Runs From the Depot Hard

Input

perm=[2, 4, 3, 5, 1]

Expected

Run checks the first 3 tests in your browser. Submit checks all 87 tests on the server, hidden ones included.