KQUERYO - K-Query Online

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 a, b, c representing a k-query. You should do the following:
    • i = a xor last_ans
    • j = b xor last_ans
    • k = c xor last_ans
    After that 1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 109 holds.
    Where last_ans = the answer to the last query (for the first query it's 0).

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:
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
hf2002: 2023-10-05 02:08:30

sqrt decomposition

karlo_2107: 2021-03-23 17:18:49

be sure that you have 1-indexed tree :)

kasparovian: 2020-10-10 13:30:43

Nice question for beginners in persistent segment tree

subhram79788: 2020-07-05 05:30:37

plz,someone explain me the 2nd query..thanks in advance ; )

ishancosmos25: 2020-05-28 13:00:37

Merge sort tree :)

nadstratosfer: 2020-05-24 15:29:10

There are AC's in Java.
https://www.spoj.com/ranks/KQUERYO/lang=JAVA

utkarsh028: 2020-05-24 08:36:56

Hi, JAVA users this question is not tested in Java. I tried
1. Persistence Seg Tree - https://pastebin.ubuntu.com/---------
2. Sqrt Decomposition - https://pastebin.ubuntu.com/------------
3. Merge Sort Tree - https://pastebin.ubuntu.com/----------------
All the solutions are giving TLE.

Last edit: 2020-05-25 08:44:22
abhishek55236: 2020-04-19 16:55:17

is there any working online solution!!

hitesh87: 2020-03-31 10:30:39

make sure to handle x>y and x>n in case using merge sort tree

sprkgoyal: 2020-01-01 05:48:44

I am getting WA, but works all my own examples..


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