KQUERY  Kquery
{assign var="code" value="KQUERY"} {if $par==""} {assign var=par value=$locale} {/if}
English  Vietnamese 
{if $par=="vn"} {literal}
Truy vấnk
Cho một dãy n phần tử a_{1}, a_{2}, ..., a_{n} và một số các truy vấnk. Một truy vấnk là một bộ ba (i, j, k) (1 ≤ i ≤ j ≤ n). Với mỗi truy vấnk (i, j, k), bạn phải trả về số phần tử lớn hơn k nằm trong dãy con a_{i}, a_{i+1}, ..., a_{j}.
Dữ liệu
 Dòng 1: n (1 ≤ n ≤ 30000).
 Dòng 2: n số a_{1}, a_{2}, ..., a_{n} (1 ≤ a_{i} ≤ 10^{9}).
 Dòng 3: q (1 ≤ q ≤ 200000), số truy vấnk.
 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ấnk (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 10^{9}).
Kết quả
 Với mỗi truy vấnk (i, j, k), in ra số phần tử lớn hơn k trong dãy con a_{i}, a_{i+1}, ..., a_{j} trên một dòng.
Ví dụ
Dữ liệu 5 5 1 2 3 4 3 2 4 1 4 4 4 1 5 2 Kết quả 2 0 3
{/literal}{elseif ($par=="en"  $par=="")}{literal}
Given a sequence of n numbers a_{1}, a_{2}, ..., a_{n} and a number of k queries. A kquery is a triple (i, j, k) (1 ≤ i ≤ j ≤ n). For each kquery (i, j, k), you have to return the number of elements greater than k in the subsequence a_{i}, a_{i+1}, ..., a_{j}.
Input
 Line 1: n (1 ≤ n ≤ 30000).
 Line 2: n numbers a_{1}, a_{2}, ..., a_{n} (1 ≤ a_{i} ≤ 10^{9}).
 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 kquery (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 10^{9}).
Output
 For each kquery (i, j, k), print the number of elements greater than k in the subsequence a_{i}, a_{i+1}, ..., a_{j} in a single line.
Example
Input 5 5 1 2 3 4 3 2 4 1 4 4 4 1 5 2 Output 2 0 3
{/literal} {/if}
hide comments
Rishabh Agrawal:
20160209 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:
20160201 09:04:53
Mo's algorithm solution.


Rishabh Agrawal:
20160130 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:
20151225 09:28:51
segment tree+ sorting in ascending+ offline processing of queries +fast i/o still TLE


Anirudh:
20151221 08:09:35
Fast I/O is a must here. 

Shivam Mitra:
20151215 21:43:20
segment tree with fast i/o gets accepted. For fast i/o in c++, refer https://discuss.codechef.com/questions/6677/coolfastioimplementation 

Additya:
20151029 15:45:40
Bit with Mo's algorithm gives TLE. Is the TL too strict? 

Abhinandan Agarwal:
20151020 00:04:28
remove spoilers please,


prakhar:
20151014 14:32:36
Segment Tree  TLE


vinorom:
20150913 08:24:47
segment tree with async IO get AC (0.34s). How do others get 0.10s? 
Added by:  Jimmy 
Date:  20081026 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Gomoku 