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 .
