I was trying to do this question https://www.codechef.com/DEC16/problems/SEAINCR/ . The question says that : Given an array of N integers and given Q queries . Each query asks you to find the length of the Longest Increasing Subsequence from index L to index R in the array. The number of test cases is T. Constraints :
1 ≤ T ≤ 10 1 ≤ A[i], Q, N Let S be sum of all A[i] in whole file. 1 ≤ S ≤ 1000000 1 ≤ L ≤ R ≤ N 1 ≤ sum of all Q per file ≤ 1000000
I have seen gvaibhav21 's solution,here. Many other people have done the same thing. I believe that they have made the DAG(Directed Acyclic Graph) of LIS problem's subproblems and have done something using it . I know how to find LIS using standard O(n^2) DP and also in O(nlogn) using binary search but i am not able to optimize it for range query . Please help as there is no editorial for this question on codechef.com .
Auto comment: topic has been updated by vivace1 (previous revision, new revision, compare).
Auto comment: topic has been updated by vivace1 (previous revision, new revision, compare).
Auto comment: topic has been updated by vivace1 (previous revision, new revision, compare).
The solution relies on the fact that sum of A[i] in the file <=10^6.
The graph: The graph is constructed in such a way that if i < j and A[i] < A[j] then there is an edge going from 'i' to 'j' iff there is no 'k' between 'i' and 'j' such that A[k] < A[j].
This graph will be constructed in O(sum of elements of array) time complexity.
let us bunch the queries, vector q[x] stores all the 'y' values such that query is for the range from index 'x' to 'y'.
Let us start considering the array elements starting from index i=n and then go till i=1 (Array 'A' is one-indexed). For each 'i', we have taken the range from 'i' to 'n' into consideration. let us define maxx[i] to be the length of LIS ending at index 'i'. when we are considering a certain index 'i' how will the values of maxx[i+1],maxx[i+2],...maxx[n] change?
It is easy to see that if some index 'j' exists such that j > i and A[j] > A[i] and that before considering i th index the value of maxx[j] was '1', then the value of maxx[j] now becomes 2.(Because now the LIS ending at index j can consist of two elements,A[i] and A[j]). maxx[j] thus now depends on maxx[i].
(note that maxx[j] can be 1 only if there is no smaller element than A[j] which is already considered before considering A[i])
But there might be some indices 'k' such that k > j where maxx[k] depended on maxx[j] so we need to change the values of maxx[all such 'k's]...then there will be some other indices which depended on maxx[k] and so we need to update those as well. The way the graph is constructed, it is easy to see that if some index 'k' is depending on index 'j' then there must be an edge from 'j' to 'k'. So with a dfs like traversal we update all the values of maxx[i+1....n] which need to be updated. see that maxx[i]=1 since it is the smallest index considered and has nothing to its left side.
So for a query from L to R all we need to do is that when we have considered the range L to n, query for the maximum value of maxx[i] for i from 1 to R (note that from 1 to L the values are zero obviously,so max in range L to R becomes same as range 1 to R).
The above range maximum query can be handled using BIT or segtree.
Thanx a lot . Got the whole logic !! :)
UPDATE : got AC using the concept you explained. Learnt a lot . Thanx a ton. Great problem indeed.
Hi can you explain the complexity of this approach. I got AC but I am not quite sure about the complexity of the algorithm.