KQUERY - K-query

no tags 

{assign var="code" value="KQUERY"} {if $par==""} {assign var=par value=$locale} {/if}

{if $par=="vn"} {literal}

Truy vấn-k

Cho một dãy n phần tử a1, a2, ..., an và một số các truy vấn-k. Một truy vấn-k là một bộ ba (i, j, k) (1 ≤ i ≤ j ≤ n). Với mỗi truy vấn-k (i, j, k), bạn phải trả về số phần tử lớn hơn k nằm trong dãy con ai, ai+1, ..., aj.

Dữ liệu

  • Dòng 1: n (1 ≤ n ≤ 30000).
  • Dòng 2: n số a1, a2, ..., an (1 ≤ ai ≤ 109).
  • Dòng 3: q (1 ≤ q ≤ 200000), số truy vấn-k.
  • Trong q dòng tiếp theo, mỗi dòng chứa 3 số i, j, k thể hiện một truy vấn-k (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 109).

Kết quả

  • Với mỗi truy vấn-k (i, j, k), in ra số phần tử lớn hơn k trong dãy con ai, ai+1, ..., aj trên một dòng.


Ví dụ

Dữ liệu
5 1 2 3 4
2 4 1
4 4 4
1 5 2 

Kết quả

{/literal}{elseif ($par=="en" || $par=="")}{literal}

Given a sequence of n numbers a1, a2, ..., an and a number of k- queries. A k-query is a triple (i, j, k) (1 ≤ i ≤ j ≤ n). For each k-query (i, j, k), you have to return the number of elements greater than k in the subsequence ai, ai+1, ..., aj.


  • Line 1: n (1 ≤ n ≤ 30000).
  • Line 2: n numbers a1, a2, ..., an (1 ≤ ai ≤ 109).
  • Line 3: q (1 ≤ q ≤ 200000), the number of k- queries.
  • In the next q lines, each line contains 3 numbers i, j, k representing a k-query (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 109).


  • For each k-query (i, j, k), print the number of elements greater than k in the subsequence ai, ai+1, ..., aj in a single line.



5 1 2 3 4
2 4 1
4 4 4
1 5 2 


{/literal} {/if}

hide comments
Rishabh Agrawal: 2016-02-09 09:12:39

@tancuong2596... Thanks for the reply. I understand your solution, but how would that ensure the O(n+q)*sqrt(n) complexity of Mo's algo... In my understanding Mo's algo sorts the queries in a particular order, so that processing them takes this complexity and not O(n^2)... But if we process the queries in order of increasing m, how would we process them in order required by Mo's. Could you pls point out what am I missing?

tancuong2596: 2016-02-01 09:04:53

Mo's algorithm solution.

An useful observation is that the answer for the query having
bigger k is also a part of the answer for the query with
smaller k.

This leads us to the algorithm: sort array of queries increasing
according to their k-value, as well as array A decreasing in
accordance with their value (we also need to store the index for
each element in the original order).

For each query (has query range [L, R] and k-value) in the new
order, we'll find all elements in A having value greater than
k-value of the query. This can be done easily because of the
decreasing order of A. Now, we are able to answer the query by
get sum of the range [L, R] in the original array.

Last edit: 2016-02-01 09:06:04
Rishabh Agrawal: 2016-01-30 00:25:08

Does anyone know of an accepted solution using MO's algorithm? I submitted using segment tree and got AC, but want to know if it can be done using MO's and how?

hello_world_v2: 2015-12-25 09:28:51

segment tree+ sorting in ascending+ offline processing of queries +fast i/o still TLE
@vinorom @Shashank Tiwari how did u get it??

Anirudh: 2015-12-21 08:09:35

Fast I/O is a must here.

Shivam Mitra: 2015-12-15 21:43:20

segment tree with fast i/o gets accepted. For fast i/o in c++, refer https://discuss.codechef.com/questions/6677/cool-fast-io-implementation

Additya: 2015-10-29 15:45:40

Bit with Mo's algorithm gives TLE. Is the TL too strict?

Abhinandan Agarwal: 2015-10-20 00:04:28

remove spoilers please,
note merge sort tree gives TLE.

prakhar: 2015-10-14 14:32:36

Segment Tree ---- TLE
MO's Algorithm(Square root Decomposition) ---- TLE
@vinorom how you did it with segment tree ??
Anyone with segment tree or an other method ??

vinorom: 2015-09-13 08:24:47

segment tree with async IO get AC (0.34s). How do others get 0.10s?

Added by:Jimmy
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET