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:
- Array is [4, 2, 3, 1, 5, 6], we have 2 queries: (1, 4, 2, 3) and (1, 6, 4, 5)
- 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.
- 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!
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.
May you elaborate how to find part1 for example using sweep line?
https://ideone.com/J2zIQj
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 $$$ \lt 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.
you can use a persistent segment tree to answer the queries online, there are plenty of tutorials online
This exact problem is a canonical problem for the Wavelet Tree — it is described in the "Range Counting" section here.
This blog is exactly what you need
https://codeforces.me/blog/entry/52854
problem link??
And there is another good problem, https://codeforces.me/contest/840/problem/D
You can solve this using merge sort tree where the time complexity can be O(q*log(n)).
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