Selecting Three People

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

The steps are as follows:

1. Create a variable named “count” to count the number of ways.
2. 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.
3. 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:

1. Create a variable named “count” to store the number of ways.
2. 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”
3. 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:

1. “cmp1” : bool cmp1(pair <int, int> p1, pair <int, int> p2)
   • This function is used in sorting the vector of pairs in decreasing order.
2. “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’.
3. “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’.
4. “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.
5. “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.
6. “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:

1. “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.
2. “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’.
3. ‘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.
4. “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.
5. “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:

1. Fill the “vLeft” and “vRight” vectors by iterating through the “arr”.
2. 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.
3. 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.
4. Iterate through the “noLeft”. (say, iterator = ‘j’)
   1. Increment “ans” by “noLeft[ i ]” * “noRight[ i ]”.
5. Return “ans”.