New update is available. Click here to update.

Last Updated: 3 Mar, 2021

Moderate

```
The first line contains a single integer βTβ representing the number of test cases.
The first line of each test case will contain a single integer βNβ, which denotes the number of people in the row.
The second line of each test case will contain βNβ integers that denote each particular personβs height in the row.
```

```
For each test case, print the number of ways to select three people according to the condition given in the description.
Output for every test case will be printed in a separate line.
```

```
You donβt need to print anything; It has already been taken care of. Just implement the given function.
```

```
1 <= T <= 10
3 <= N <= 100
1 <= ARR[i] <= 10 ^ 5
Where 'ARR[i]' denotes the height of the i-th people in the row.
Time limit: 1 sec
```

Approaches

The basic idea is to iterate through all possible triplet of people in the row using three loops.

**The steps are as follows:**

- Create a variable named βcountβ to count the number of ways.
- Iterate through βarrβ (say, iterator = βiβ)
- Iterate through βarrβ from (βiβ + 1) to the end of the ARR (say, iterator = βjβ)
- Iterator through βarrβ from (βjβ + 1) to the end of the ARR (say, iterator = βkβ)
- Check if arr[ i ] < arr[ j ] < arr[ k ] then increment the βcountβ by 1.

- Iterator through βarrβ from (βjβ + 1) to the end of the ARR (say, iterator = βkβ)

- Iterate through βarrβ from (βiβ + 1) to the end of the ARR (say, iterator = βjβ)
- Return βcountβ.

The basic idea of this approach is to calculate the number of possible triplets of people, which follows the required condition by calculating the number of people with less height than the βi-thβ people on his left side and the number of people with greater height on his right side.

**The steps are as follows:**

- Create a variable named βcountβ to store the number of ways.
- Iterate through the βarrβ (say, iterator = βiβ)
- Create two variables (say, βleftβ and βrightβ) to store the number of people with less height in the left of people at βiβ and the number of people with greater height in the right of people at βiβ.
- Iterate again through the βarrβ (say, iterator = βjβ)
- Check if, βjβ is less than βiβ and arr[ j ] is also less than the arr[ i ] then increment βleftβ by 1.
- Check if, βjβ is greater than βiβ and arr[ j ] is also greater than the arr[ i ] then increment βrightβ by 1.

- βcountβ = βcountβ + βleftβ * βrightβ

- Return βcountβ.

The basic idea of this approach is to pre-calculate the number of people with less height on the left side of each individual people and the number of people with the greater height on the right side of each people, this is done by using a segment tree first for the left side and then for the right side. Here, the elements of the array are not changing and so, we will use the offline approach.

**Additional Functions Used:**

**βcmp1β**: bool cmp1(pair <int, int> p1, pair <int, int> p2)- This function is used in sorting the vector of pairs in decreasing order.

**βcmp2β**: bool cmp2(vector<int> v1, vector<int> v2)- This function is used to sort the vectors of a vector in increasing order according to the value stored at the third index in the vector βv1β and βv2β.

**βcmp3β**: bool cmp2(vector<int> v1, vector<int> v2)- This function is used to sort the vectors of a vector in decreasing order according to the value stored at the third index in the vector βv1β and βv2β.

**βbuildβ**: void build(vector<int> & st, int ss, int se, int i)- This function is used to build the segment tree.
- It takes arguments as, βstβ - tree array, βssβ - segment start index, βseβ - segment end index, and βiβ - current index of the tree array.
- This function set the value 1 at each node in the segment tree.

**βupdateβ**: void update(vector<int> & st, int ind, int ss, int se, int i)- This function is used to update the value of nodes in the segment tree.
- It takes arguments as, βstβ - tree array, βindβ - index whose value have to be updated, βssβ - segment start index, βseβ - segment end index, and βiβ - current index of the tree array.

**βqueryβ**: int query(vector<int> & st, int qs, int qe, int ss, int se, int i)- This function returns the result of the query asked in the given range.
- It takes arguments as, βstβ - tree array, βqsβ - starting index of the query, βqeβ - ending index of the query, βssβ - segment start index, βseβ - segment end index, and βiβ - current index of the tree array.
- It basically returns the value obtained after adding the value of each node that lies in the range from βqsβ to βqeβ.

**Additional Variables Used:**

**βvLeftβ and βvRightβ**: These two are the vectors of type pair<int, int> that will be used to store the height of each individual person along with their positions.- βvLeftβ will be sorted by using the βcmp1β function and it is used in calculating the number of people having the height less than the βi-thβ people.
- βvRightβ will be sorted in increasing order and it is used in calculating the number of people having a height greater than the βi-thβ people.

**βstβ**: This is a vector of type int which represents the tree array or we can say the segment tree. It is of size 4*βNβ.**βqβ**: This is a vector of vectors that represents the queries that need to be executed to calculate the number of people having heights less or greater than the height of the βi-thβ people.**βnoLeftβ and βnoRightβ**: These are the two vectors of type int that will be used to store the number of people (having less height) on the left of the people at position βiβ and the number of people on the right (having greater height), respectively.**βansβ**: It is a variable of type int that will be used to store the number of triplets of the people who follow the required conditions.

**The steps are as follows:**

- Fill the βvLeftβ and βvRightβ vectors by iterating through the βarrβ.
- For calculating the number of people having less height than people at βiβ.
- Sort the βvLeftβ according to the function βcmp1β.
- Iterate through the βarrβ from 0 to βNβ - 3. (say, iterator = βiβ)
- Add a query in the βqβ that has a starting index as 0, ending index as βiβ, particular people (with respect to which we want to calculate people having fewer heights) as βarr[ i + 1]β, and query index as βiβ.

- Sort βqβ according to the function βcmp2β.
- Now, build the segment tree by using the βbuildβ function and passing arguments as βstβ = βstβ, βssβ = 0, βseβ = βNβ - 1, and βiβ = 0.
- Create a pointer variable βposβ and set it to 0.
- Iterate through the queries. (say, iterator = βiβ).
- And, keep calling the function βupdateβ and increment βposβ by 1 if, βposβ < βNβ and βvLeftβ at βposβ is greater than or equal to the value at index 2 in βq[i]β. This step is done to remove the people from the range that have a greater height than the people at βq[i][2]β.
- As βqβ is sorted in the decreasing order of required people and so, it is guaranteed that the people in βvLeftβ that have a height greater than the βq[i-1][2]β must also have height greater than the βq[i][2]β.
- Now, call the function βqueryβ by passing arguments as βstβ = βstβ, βqsβ = βq[i][0]β, βqeβ = βq[i][1]β, βssβ = 0, βseβ = βNβ - 1, and βiβ = 0. Store the result of this query into the βnoLeftβ vector.

- For calculating the number of people having less height than people at βiβ.
- Sort the βvRightβ in increasing order.
- Clear the βqβ.
- Iterate through the βarrβ from 2 to βNβ - 1. (say, iterator = βiβ)
- Add a query in the βqβ that have starting index as βiβ, ending index as βNβ - 1, particular people (with respect to which we want to calculate people having greater heights) as βarr[ i - 1]β, and query index as βiβ - 2.

- Sort βqβ according to the function βcmp3β.
- Now, build the segment tree again by using the βbuildβ function and passing arguments as βstβ = βstβ, βssβ = 0, βseβ = βNβ - 1, and βiβ = 0.
- Reset the pointer variable βposβ to 0.
- Iterate through the queries less than or equal to the value at index 2 in βq[i]β. This step is done to remove the people from the range that have less height than the people at βq[i][2]β.
- As βqβ is sorted in the increasing order of required people and so, it is guaranteed that the people in βvRightβ that have a height less than the βq[i-1][2]β must also have height less than the βq[i][2]β.
- Now, call the function βqueryβ by passing arguments as βstβ = βstβ, βqsβ = βq[i][0]β, βqeβ = βq[i][1]β, βssβ = 0, βseβ = βNβ - 1, and βiβ = 0. Store the result of this query into the βnoRightβ vector.

- Iterate through the βnoLeftβ. (say, iterator = βjβ)
- Increment βansβ by βnoLeft[ i ]β * βnoRight[ i ]β.

- Return βansβ.

Similar problems

Ninja And The LCM

Easy

Posted: 12 Apr, 2022

A Number Game

Moderate

Posted: 23 Apr, 2022

Pair Product Div by K

Moderate

Posted: 15 May, 2022

Pair Product Div by K

Moderate

Posted: 15 May, 2022

Merge Two Sorted Arrays Without Extra Space

Moderate

Posted: 19 Nov, 2022

Co-Prime

Hard

Posted: 14 Dec, 2022