I recently asked a question on cs.stackexchange, but since I got no answers there, I figured I should ask here too :)
The problem is the following: We are given a set of intervals (if you want, make it empty in the beginning). Then we have $$$Q$$$ queries, which are of one of the following types:
- Add a new interval to the set
- For a given query interval $$$[l_i, r_i]$$$, find the length of the longest interval from the set which is contained entirely inside $$$[l_i, r_i]$$$.
As mentioned in the linked question, if we didn't have query type 1, we can do a persistent segment tree and handle the queries. I have also been thinking we can do SQRT decomposition and answer in $$$O(Q\sqrt Q)$$$. Is there a better algorithm? I would like to be able to do this in $$$O(Q \log Q)$$$ or $$$O(Q \log^2 Q)$$$
