I was doing this question Hotel Queries on CSES. I understand the obvious Nlog^2N approach that uses binary search on segment trees.

But I'm interested in solving it in NlogN and I know the fractional cascading approach that traverses the segment tree. But I want to try this approach on an iterative segment tree ,exactly the same implementation as in the blog Efficient and easy segment trees.

But apparently the tree from this version of the segment tree is degenerate where we cannot guarantee that the left child corresponds to an actual left range. i.e it is not necessary for the left child to have range [l1,r1] such that r1>l2 for the corresponding right child.

Please share any implementations of fractional cascading or any NlogN approaches you know using iterative segment tree for the problem.

Given N dolls of dimensions (wi,hi), i.e w corresponds to width of ith doll and hi corresponds to height of ith doll. Now we can stuff a doll with dimensions (wx,hx) inside another (wy,hy) if wx<wy and hx<hy. Also you cannot change the order i.e x<y. Now if we can stuff a doll A under doll B, then B is said to be increasing with respect to A. Find the largest increasing subsequence.

1<=N<=100000 1<= wi,hi<= 1e9

Note:This is similar to the problem "Russian doll Envelopes" from leetcode ,but with added constraints(order is forced).