achhadahappy's blog

Needed help for query based question
By achhadahappy, history, 21 month(s) ago, In English

You will be given an array and some queries. Each query will contain three integers l, r, and x. You have to return the count of the integer in array in the range [l,r] whose value is less than or equal to x. for example n=7 q=2 5 4 8 7 6 2 1 1 3 5 2 5 6

ans = 2 2

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

»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

You can use a merge sort tree or a wavelet tree

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Persistant segment tree works ig

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

You can convert it into a three-dimensional partial order, and then use the Binomial theorem to solve it in n log n (not n log^2 n)

→ Reply