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
sajib_only:
20170703 18:43:07
Don't know what was the problem with this problem. I thought I will get WA but got AC. have many questions.


prakhar10_10:
20170628 06:53:04
The test data is still wrong I think. 

tawhidkuet04:
20170425 08:35:01
Can be easily done by segment tree with vectors. 

Ashwani Gautam:
20170326 07:36:22
Test data is now correct! got AC without handling Blue.Mary assumptions.


kunalk:
20170315 20:43:31
can someone please explain how to solve it with sqr_root decomposition ?? 

Abhishek Kainth:
20161230 18:32:54
Thanks @[Rampage] Blue.Mary


mahmood_2000:
20161105 10:09:34
Great problem for learning sqr_root decompostion but watch out you have to use fast i/o (i.e in c++ I had to use scanf and printf to get AC)


sekhar162:
20160903 22:42:15
do it in 1 based indexing... 

secta:
20160729 14:01:16
Why am I not shown on the ranking, I have an accepted solution running in 0.08? 

[Rampage] Blue.Mary:
20160121 04:30:15
OK. The test data seems not satisfy the conditions mentioned in problem description. I assume the following:

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