Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Range query to find Longest Increasing Subsequence Please Help
Difference between en3 and en4, changed 12 character(s)
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 [user:gvaibhav21,2017-06-18] 's solution,[here](https://www.codechef.com/viewsolution/12180064). 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 .

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English vivace1 2017-06-19 07:23:12 12
en3 English vivace1 2017-06-19 07:18:43 9
en2 English vivace1 2017-06-18 22:29:05 58
en1 English vivace1 2017-06-18 22:23:13 974 Initial revision (published)