achhadahappy's blog

Needed help for query based question
By achhadahappy, history, 19 months 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

»
19 months ago, # |
  Vote: I like it +8 Vote: I do not like it

You can use a merge sort tree or a wavelet tree

→ Reply
»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Persistant segment tree works ig

→ Reply
»
19 months 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