DEC16 long challenge was the first long challenge after i started taking competitive programming seriously. I want to know how to solve the problem SEAINCR from this challenge . The problems asks Q queries( Q <= 10^5) to find out the length of the longest increasing subsequence(LIS) from L to R indices in an array .
What i could manage till now :
Subtask 1 : 15 points (done using LIS in O(n^2) per query)
Subtask 2 : 15 points (done using LIS in O(nlogn) per query)
I could not solve the SUBTASK 3 : 70 points and I need the approach for that. I am familiar with fenwick trees(Binary Indexed Trees/BIT) as well as segment trees but i couldn’t think of anything using them in this question.