KQUERYO  KQuery Online
Given a sequence of n numbers a_{1}, a_{2}, ..., a_{n} and a number of kqueries. 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 a, b, c representing a kquery. You should do the following:
 i = a xor last_ans
 j = b xor last_ans
 k = c xor last_ans
Where last_ans = the answer to the last query (for the first query it's 0).
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: 6 8 9 3 5 1 9 5 2 3 5 3 3 7 0 0 11 0 0 2 3 7 4 Output: 1 1 0 0 2
[Edited by EB]
There are invalid queries. Assume the following: if i < 1: i = 1
 if j > n: j = n
 if i > j: ans = 0
hide comments
louhc:
20190119 16:08:41
forget continuing...... silly me 

a_98:
20190101 12:16:12
Persistent Segment Tree + Binary Search does it ! 

Erick:
20180828 07:14:00
Finally AC!


tisparta:
20180809 05:43:20
Also solvable with Wavelet tree e.e 

amulyagaur:
20180314 07:12:34
same concept can be applied here as well:


madhur4127:
20180226 14:50:18
O(sqrt(N)*log(N)) gives AC in 0.12s, how to reduce time other than using merge sort tree? 

ayushgupta1997:
20180222 14:05:42
The test cases are weak sqrt decomp also passes...even i didn't use long long for a[] still passed :( 

ramini1996:
20180205 11:05:10
AC in ONE GO !!! 

shiv2111:
20180112 10:32:34
same version KQUERY has very strict TL, merge sort tree is not going to work there. 

sherlock726:
20171016 20:56:51
ac on first go

Added by:  amirmd76 
Date:  20150417 
Time limit:  0.200s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 