Блог пользователя I_love_Saundarya

How to find the count of numbers less than 'k' in a given range of array?

Автор I_love_Saundarya, история, 5 лет назад, По-английски

Given multiple queries of the form : "L R k" , how to find the count of numbers less than 'k' in the range {L,R} of the array.

There are no update queries.

N=1000000.

I am not interested in the solution with a merge-sort-tree .

  • Проголосовать: нравится
  • -18
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Constraints?

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

What is the source of this problem? Please provide a link if possible.

→ Ответить
»
5 лет назад, # |
← Rev. 6   Проголосовать: нравится +11 Проголосовать: не нравится

If you can process the queries offline you should sort all of the values in the array. After that let's iterate over the sorted values, and add 1 to it's original position in the array using a segment tree, when all values < some k have been added, the answer for the query with that k is the sum on the query's range. Each query costs us log(n) to process thus this approach solves the problem in O(nlogn).

If you can't sort the queries offline, i sugest building a mergesort tree over the original array. In each node of the tree you will keep the values of that node's subarray sorted. Now for each query you will need to decompose the range into base nodes, and for each node binary search the number of values <k.' Building the mergesort tree takes nlogn time, and each query can be answered in logn^2, so the total time complexity is O(nlog(n)^2) This approach can also be used to handle updates. To do this you have to keep a binary search tree in each node instead of a sorted array.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    What is a mergesort tree ?

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      Basically divide the elements in segments like in a segment tree and for every node you keep all the values in that range sorted. When you do a query like :"number of elements between a and b from l to r" you use the same idea of segment tree to choose the segments and after that you can use binary search to count the number of elements in every range that you are interested in.

      → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      I just wrote this code for a merge sort tree that support the query that you wanted.

      #include<bits/stdc++.h>
using namespace std;
template <class t> class MergeSortTree{
	public:
		int _l, _r, _m;
		vector<t> v;
		MergeSortTree *left, *right;
		MergeSortTree(int l, int r, vector<t> &e){
			_l=l, _r=r, _m=(l+r)/2, v[0]=e[l];
			v.resize(r-l+1);
			if(l==r)	left=right=nullptr;
			else{
				left=new MergeSortTree(_l,_m, e);
				right=new MergeSortTree(_m+1,_r, e);
				merge(left->v.begin(), left->v.end(), right->v.begin(), right->v.end(), v.begin());
			}
		}
		int count(int l, int r, t a, t b){ //Number of x -> a<=x<=b and x is between l and r
			if(l>_r || r<_l) return 0;
			if(_l>=l && _r<=r)	return upper_bound(v.begin(), v.end(), b)-lower_bound(v.begin(), v.end(), a);
			return left->count(l,r,a,b)+right->count(l,r,a,b);
		}
};
int main(){
	vector<int> v={1,5,2,7,4,1};
	MergeSortTree<int> mt(0,v.size()-1,v);
	cout<<mt.count(0,v.size()-1,0,7);
}

      Using algorithm's functions the code, as you can see, is really short.

      → Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

You can use policy based data structure to solve this question (ordered_set) in O(N*logN).

You can refer to this link to look at this data structure. https://codeforces.com/blog/entry/11080

You can also solve it using SQRT Decomposition but you need to be careful about the time limit.

→ Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

If you really wanna get to it... you can turn each element into a point (i, a[i]) and use an implicit 2d segment tree to query for points in the region where x is [l, r] and y is [k, infinity). O(n log^2 n)

Merge sort tree has same time complexity and MUCH better constant factor

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

We can solve this problem Offline. First, sort the queries in increasing order and the values of the array as {value,index}. For each query ,using a data structure which can do sums and update operations (eg segment tree or bit), set to one the all the indices which have value < K of the current query and >= K of the previous query .As you have done this for previous queries the sum query will take into account all values < K.the answer of i'th query is sum(l,r) after performing updates. Here's my submission for a similar problem.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Wavelet tree can solve online version of this problem in O(n*log(maxA)) and offline version in O(n*log(n)) (using compression).
Useful links:
Errichto's wavelet tree tutorial on YouTube
Codeforces blog with implementation

→ Ответить