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.