PROBLEM LINK:Author: Konstantsin Sokol DIFFICULTY:Mediumhard. PREREQUISITES:Dynamic Programming, Binary Indexed Trees. PROBLEM:You are given a sequence $a_1, a_2, ..., a_N$ of nonnegative 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,
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:
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
Suppose we fix $L$ and process the elements from left to right until $N$. For each $x$ up to $N$,
This preprocessing takes $O(N^2 log N)$ time because we do 4 inserts and updates in BITs for each valid interval $[L, R]$. After this preprocessing, 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:
AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 19 Apr '15, 22:00

Can anyone please tell me why did I get a TLE for my O(N*Q) solution : http://www.codechef.com/viewsolution/6798568 , when there is an accepted solution of the same complexity on the first page itself : http://www.codechef.com/viewsolution/6799042 answered 20 Apr '15, 02:57
2
There are a lot of optimizations in the accepted solution that you have shown.
(21 Apr '15, 13:28)

Hi @Tester ! I'm a newbie to advanced datastructres and I went through BIT explanations and understood it's working. I read your solution and there was one section I couldn't understand. :/ I understood the working of the init() function. In the array a[] you have stored (all the elements of the input array that is <= ith element of the input array) Now, you have created 4 fenwick / BIT trees according to the above mentioned rules in the editorial. but I don't understand the working of the following code:
I'll be glad if you can help me in this. :) Thanks. answered 21 Apr '15, 11:38
Part2/2 A simpler option is to transform the numbers. Say the maximum number is 100. If we had [100, 2, 50, 10], For b = 10, the numbers higher than b are 100 and 50. Let's transform the numbers into Max  v[i] + 1, getting [1, 99, 51, 91]. now the former 10 is 91 (10010+1). The numbers lower than 91 are the numbers that were > 10 in the original sequence, 100 is 1 and 50 is 51. So, we can now use the same technique as for increasing subsequences.
(21 Apr '15, 15:45)
Part1/2 A BIT query(x) allows us to know how many items are there up to "x". Suppose we want to count increasing subsequences like "a < b". We have b = 10, so we just need to know how many numbers are in the BIT that are less than 10, which is Query(b1) = Query(9). Suppose now that we want to count decreasing subsequences. "a > b". We want how many numbers are there larger than 10. This is not so convenient using a BIT. One option would be to have the total amount of numbers and subtract the numbers up to 10, like "Total  Query(b)". (continue in next comment)
(21 Apr '15, 15:45)
Hi, Thanks for your explanation but I'm still having some doubts in it. Let me ask you pointwise:
Insert(lim  a[l], 1, tree[0]); for (int j = l + 1; j < n; ++j) { ans[l][j] = Query(a[j]  1, tree[3]); Insert(a[j], Query(lim  a[j]  1, tree[2]), tree[3]); Insert(lim  a[j], Query(a[j]  1, tree[1]), tree[2]); Insert(a[j], Query(lim  a[j]  1, tree[0]), tree[1]); } Thanks.
(21 Apr '15, 18:12)
About 1) BIT_r is tree[3], BIT_k is tree[2], BIT_j is tree[1] and BIT_i is tree[0] About 2) each line of code does what the editorial mentions in the bullet points after "Suppose we fix L". Could you be more specific on what you didn't understand?
(21 Apr '15, 19:04)
I'm sorry to trouble you so much with my doubts. I'm really thankful for your help. :) I don't understand this part specifically in the editorial I guess. Use BIT_i to count the number of integers such that ai<aj. Update BIT_j with this number. Insert ax to BIT_i How exactly are we using BIT_i to count the number of integers such that ai < aj. What is i and j here? Are they any two indices between L and index[ax] ? If I get this then I guess it must be the same for updating other trees.
(21 Apr '15, 21:01)
Ah, I see. We are processing the elements from left to right. Something like for (L = 0; L < N; L++) {
} } "ax" is a[ x ] and by "ai" I mean any index between in [L+1 , x1]. Inserting "ax" in the BIT is a normal BIT update increasing the frequency of integer a[ x ] by 1. To know the number of integers less than a[ x ], we can use Query(a[ x ]  1) on the BIT.
(21 Apr '15, 21:23)
showing 5 of 6
show all

I tried solving in N*Q operations the queries with a processing of N^2 logN .But I continuously got WA. Can anyone tell me the mistake?? My code : http://www.codechef.com/viewsolution/6799654 answered 21 Apr '15, 12:06

can someone tell why I am getting a wa for this solution http://www.codechef.com/viewsolution/6937555 answered 15 May '15, 02:46

just an opinion .. for future questions, please don't keep such constraints.. O(NQ) passes with fast IO .. keeping Q to be 5*10^5 would have been perfect i guess.
can someone please give more insight on how the 4 binary indexed trees coordinate to get the correct answer.