KQUERY  Kquery
English  Vietnamese 
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
hide comments
RISHAV KUMAR:
20161001 00:31:40
Has anyone done it in java using BIT..? I'm getting TLE, while the same code in c++ is getting passed. such a pain.. Last edit: 20161001 00:31:57 

divide_by_1:
20160829 06:32:59
Did some one got AC with sqrt decomposition ? 

buttman:
20160718 16:19:16
time limit should be increased a bit. 

askerov:
20160707 17:19:18
I wrote Segment Tree, but it doesn't work. I have got TLE. What is Time limit: 0.184s? only build gets 0.2s 

proficient:
20160525 16:49:56
Anyone got AC with O( Q log^2 (N) ) ? I get TLE even with fast IO, typedef and inline functions. 

N0VICE:
20160227 09:53:47
Very strict Time Limit...


Vinicius Zibetti Resko [UNITAU]:
20160217 21:38:02
Very strict TL, my q * log (n+q) solution gives TLE even with fast I/O. 

Vipul:
20160217 13:47:01
nice problem


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.

Added by:  Duc 
Date:  20081026 
Time limit:  0.184s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  © VNOI 