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 .

# | User | Rating |
---|---|---|

1 | Benq | 3783 |

2 | jiangly | 3772 |

3 | tourist | 3706 |

4 | maroonrk | 3609 |

5 | Um_nik | 3591 |

6 | fantasy | 3526 |

7 | ko_osaga | 3500 |

8 | inaFSTream | 3477 |

9 | cnnfls_csy | 3427 |

10 | zh0ukangyang | 3423 |

# | User | Contrib. |
---|---|---|

1 | Um_nik | 183 |

2 | awoo | 180 |

3 | nor | 172 |

4 | -is-this-fft- | 171 |

5 | adamant | 170 |

6 | maroonrk | 165 |

7 | antontrygubO_o | 161 |

8 | SecondThread | 159 |

9 | dario2994 | 152 |

9 | kostka | 152 |

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 .

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/21/2023 17:24:29 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Constraints?

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

https://www.spoj.com/problems/KQUERY/

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.

What is a mergesort tree ?

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.

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

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

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.

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

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.

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