Hi, I am having difficutlties with this CSES problem "Book Shop". Firstly I implemented it recursively, but it gave me TLE. (Link). I've also been trying to get into iterative dp, so I tried it too and it worked! (Link)

However, I don't understand why recursive approach doesn't pass. Maybe I have implemented it poorly?

Also, it seems that there is an approach with $$$O(x)$$$ space complexity, but I have no clue how it works.

This is my first entry here, but I have a problem as follows: You are given $$$N$$$ intervals denoted $$$(x,y)$$$, $$$(1 \leq N \leq 10^5)$$$ and $$$(1 \leq x \leq y \leq 10^5)$$$. Answer $$$Q$$$ queries in the form $$$(l,r)$$$, $$$(1 \leq Q \leq 10^5)$$$ and $$$(1 \leq l \leq r \leq 10^5)$$$, find the number of intervals completely lying in the given range, that is $$$l \leq x_i \leq y_i \leq r$$$.

So, this is basically a problem of finding the number of segments lying in the given range.

I think that this problem can be solved using Mo's Algorithm in something like $$$O(Q\sqrt{N})$$$.

But if it was just to find the count of given numbers in the given segment, I would've just used Prefix Sum array and answer queries in $$$O(1)$$$. Can there be something similar to this? Or Mo's Algorithm (if I'm not mistaken) is the best here?