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


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.

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