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
sherlock726: 2017-10-16 20:56:51

ac on first go
simple segment tree + vector for each node

sajib_only: 2017-07-03 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.
#are the i and j 0 based or 1 based? (i got AC with assuming 1 based but i don't know what happens if we get 0 after XOR :3 )
#got a WA when i tool 4*30000 + 10 as size of the Segment Tree Array. then when i made it 4*300000 + 10 , it passed smoothly with AC

prakhar10_10: 2017-06-28 06:53:04

The test data is still wrong I think.

tawhidkuet04: 2017-04-25 08:35:01

Can be easily done by segment tree with vectors.

Ashwani Gautam: 2017-03-26 07:36:22

Test data is now correct! got AC without handling Blue.Mary assumptions.
sqrt_decomposition have O(ROOT(N)) time per query. should not pass. Unless heavily optimized

kunalk: 2017-03-15 20:43:31

can someone please explain how to solve it with sqr_root decomposition ??

Abhishek Kainth: 2016-12-30 18:32:54

Thanks @[Rampage] Blue.Mary
Your assumptions were right

mahmood_2000: 2016-11-05 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: 2016-09-03 22:42:15

do it in 1 based indexing...

secta: 2016-07-29 14:01:16

Why am I not shown on the ranking, I have an accepted solution running in 0.08?


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