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.
I’m a newbie to advanced data-structres 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’ll be glad if you can explain a little bit further
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 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 : CodeChef: Practical coding for everyone
@tester
I am new at advanced data structures and I am trying to understand this program. I got most of it but I have a few queries.
What does the Insert statement of the outer for loop tell? Why we take Insert(lim-a[l],1,tree[0])?
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.
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(b-1) = 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)”.
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 (100-10+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.
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?
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.
Can someone please help me. Despite of the answers above I have still no clue how to update BIT_j. Can someone explain the procedure with the following integers 4 3 2 1 4 ? How should BIT_j and BIT_k look like in every step?
