drugkeeper's blog

Problem: Counting the number of elements in an array from l to r with a value from v1 to v2
By drugkeeper, 18 months ago, In English

I am not sure how to find an efficient solution to this problem that I just thought of:

Problem: Given an unsorted array of length n of integers (each integer is up to 10^9), you need to perform q queries. Each query is of the form (l, r, v1, v2), where you need to count the number of elements in the array from index l to r, having a value of v1 <= x <= v2.

Constraints: 1 <= l, r, n, q <= 10^5, 1 <= v1 <= v2 <= 10^9.

Example:

  1. Array is [4, 2, 3, 1, 5, 6], we have 2 queries: (1, 4, 2, 3) and (1, 6, 4, 5)
  2. For the first query, output 2, because we have 2 elements in the subarray [4, 2, 3, 1] with a value from 2 to 3.
  3. For the next query, output 2, our subarray is [4, 2, 3, 1, 5, 6], we have 2 elements with a value from 4 to 5.

Is there a fast way to solve this problem?

For v1 == v2 (aka, if we are just counting the number of elements from l to r with count of v), we can just make 1 dictionary for each element, every 2 elements, every 4 elements and so on like a segment tree of dictionaries, then when we query l and r we can find the number of elements in that range.

However if v1 != v2 I do not know of an efficent way, please help!

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

Comments Comments (10)
| Write comment?
»
18 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

answer to each query of form (l,r,v1,v2) is (# elements in range [1,r] with value <= v2) — (# of elements in range [1,l] with value < v1) we can process part1 and part2 of above independently using technique like sweep line.

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    May you elaborate how to find part1 for example using sweep line?

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      https://ideone.com/J2zIQj

      → Reply
    • »
      »
      »
      18 months ago, # ^ |
      ← Rev. 3   Vote: I like it +21 Vote: I do not like it

      A hint is to imagine placing the elements in the array from lowest to highest (putting smaller elements first in their positions). After putting all the elements with values $$$< v1$$$. (An element $$$A(i)$$$ is placed means $$$B(i)=1$$$, otherwise $$$B(i)=0$$$). Just find the subarray sum of the range $$$[L,R]$$$ in array $$$B$$$. This is will the count of elements in range $$$[1,v1-1]$$$ in subarray $$$[L,R]$$$ of array $$$A$$$.

      Similarly do the same when you have placed all the elements $$$\le v2 $$$. You will require a point update and range sum Fenwick or segment tree for this.

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

you can use a persistent segment tree to answer the queries online, there are plenty of tutorials online

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

This exact problem is a canonical problem for the Wavelet Tree — it is described in the "Range Counting" section here.

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

This blog is exactly what you need

https://codeforces.me/blog/entry/52854

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem link??

And there is another good problem, https://codeforces.me/contest/840/problem/D

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

You can solve this using merge sort tree where the time complexity can be O(q*log(n)).

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If TL is high enough (maybe 5s enough?), it can be solved using Mo' algo + BIT in $$$O(n \sqrt{n} logn)$$$ . First compress the values, then apply mo's algo. When you add a new value increase its value in BIT by 1, decrease by 1 otherwise. Then get the sum of range [v1,v2] using BIT

→ Reply