TheAiro's blog

By TheAiro, history, 21 month(s) ago, In English

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?

  • Vote: I like it
  • +8
  • Vote: I do not like it

| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Or Mo's Algorithm (if I'm not mistaken) is the best here?

Hm. You could sort all given intervals by $$$x$$$ and all given queries by $$$l$$$ (thus offline solution as MO's Algorithm) and use Fenwick Tree for counting (adding $$$1$$$ on each $$$r$$$, then substracting $$$1$$$ for the intervals with $$$x < l$$$), reaching $$$O(nlogn + qlogq + qlogn + 10^5)$$$.