### PROBLEM LINK:

**Author:** Konstantsin Sokol

**Tester:** Gedi Zheng

**Editorialist:** Miguel Oliveira

### DIFFICULTY:

Medium-hard.

### PREREQUISITES:

Dynamic Programming, Binary Indexed Trees.

### PROBLEM:

You are given a sequence a_1, a_2, ..., a_N of non-negative integers. Your task is to process Q queries of the following format: each query is described by two integers L ≤ R and asks to calculate the number of triples (i, j, k), such that L < i < j < k < R and a_L > a_i < a_j > a_k < a_R.

### EXPLANATION:

The first thing to notice is that there are repeating patterns in the subsequences. For example,

- Increasing subsequences like a_i < a_j and a_k < a_R
- Decreasing subsequences like a_L > a_i and a_j > a_k
- Triples a_L > a_i < a_j and a_j > a_k < a_R

So, suppose we process the sequence from left to right. We can break down the triplets such that a_L > a_i < a_j > a_k < a_R, with L < i < j < k < R, in parts:

- For a fixed R, the number of subsequences a_L > a_i < a_j > a_k < a_R is the number of subsequences a_L > a_i < a_j > a_k such that a_k < a_R
- For a fixed k, the number of subsequences a_L > a_i < a_j > a_k is the number of subsequences a_L > a_i < a_j such that a_j > a_k
- For a fixed j, the number of subsequences a_L > a_i < a_j is the number of subsequences a_L > a_i such that a_i < a_j
- The number of subsequences such that a_L > a_i is the number of integers between L and j below a_L

Hence, we can build up on the smaller parts in order to find the solution for each query.

We can use a binary indexed tree (BIT) to keep counts for each part

- BIT_r counts how many subsequences a_L > a_i < a_j > a_k are there where a_k equals a query value.
- BIT_k counts subsequences a_L > a_i < a_j.
- BIT_j counts subsequences a_L > a_i.
- BIT_i counts the frequency of integers seen so far.

Suppose we fix L and process the elements from left to right until N. For each x up to N,

- Use BIT_r to count the number of subsequences a_L > a_i < a_j > a_k up to x, such that a_k < a_x. The answer to a query in interval [L, x] is this value. Save this in a table.
- Use BIT_k to count the number of subsequences a_L > a_i < a_j, such that a_k > a_x. Update BIT_r with this number.
- Use BIT_j to count the number of subsequences a_L > a_i, such that a_j < a_x. Update BIT_k with this number.
- Use BIT_i to count the number of integers such that a_i < a_j. Update BIT_j with this number.
- Insert a_x to BIT_i

This pre-processing takes O(N^2 log N) time because we do 4 inserts and updates in BITs for each valid interval [L, R].

After this pre-processing, we can answer any query using the computed table in O(1) time.

Thus, the total time complexity is O(N^2 \log N + Q).

Implementation notes:

- Since the input numbers can be up to 10^9, we should pre-process them and compress the values in a range [1, N] (we don’t care about the number itself, just their relative order)
- Instead of implementing separate Binary Indexed Trees for increasing and decreasing subsequences, we can just check for increasing subsequences. To do this, note that we can transform a decreasing subsequence into an increasing one by changing each value a{_i} to maxvalue - a_i.