KQUERY - K-query

no tags 

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.

Input

  • 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).

Output

  • 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.

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: 2016-10-01 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: 2016-10-01 00:31:57
divide_by_1: 2016-08-29 06:32:59

Did some one got AC with sqrt decomposition ?

buttman: 2016-07-18 16:19:16

time limit should be increased a bit.

askerov: 2016-07-07 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: 2016-05-25 16:49:56

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

||N0VICE||: 2016-02-27 09:53:47

Very strict Time Limit...
finally solved using segment tree(QlogQ + Qlogn) with fast io

Vinicius Zibetti Resko [UNITAU]: 2016-02-17 21:38:02

Very strict TL, my q * log (n+q) solution gives TLE even with fast I/O.

Vipul: 2016-02-17 13:47:01

nice problem
O(q log^2(n))(even with fast I/O).....TLE
O(q log n)(with segment tree).....TLE
O(q log n)(with BIT)....AC

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

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