KQUERY - K-query

no tags 

{assign var="code" value="KQUERY"} {if $par==""} {assign var=par value=$locale} {/if}

{if $par=="vn"} {literal}

Truy vấn-k

Cho một dãy n phần tử a1, a2, ..., an và một số các truy vấn-k. Một truy vấn-k là một bộ ba (i, j, k) (1 ≤ i ≤ j ≤ n). Với mỗi truy vấn-k (i, j, k), bạn phải trả về số phần tử lớn hơn k nằm trong dãy con ai, ai+1, ..., aj.

Dữ liệu

  • Dòng 1: n (1 ≤ n ≤ 30000).
  • Dòng 2: n số a1, a2, ..., an (1 ≤ ai ≤ 109).
  • Dòng 3: q (1 ≤ q ≤ 200000), số truy vấn-k.
  • Trong q dòng tiếp theo, mỗi dòng chứa 3 số i, j, k thể hiện một truy vấn-k (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 109).

Kết quả

  • Với mỗi truy vấn-k (i, j, k), in ra số phần tử lớn hơn k trong dãy con ai, ai+1, ..., aj trên một dòng.

     

Ví dụ

Dữ liệu
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2 

Kết quả
2
0
3 

{/literal}{elseif ($par=="en" || $par=="")}{literal}

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 i, j, k representing a k-query (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 109).

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
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2 

Output
2
0
3 

{/literal} {/if}


hide comments
dragon_162: 2017-12-30 12:02:48


Last edit: 2018-02-05 16:33:08
karthik1997: 2017-12-29 16:54:08

Segment tree 0.15 and BIT 0.10 with fast i/o . Cant go below it :( . How could people get below 0.1s :O

lostground97: 2017-12-21 10:27:58

Can this be done using Normal Segment Tree?
Getting TLE while using multiset to store elements for each segment!

shubhamkr2020: 2017-12-18 12:45:06

accepted using printf but tle using cout.
lolololol....

ashutosh_gajre: 2017-12-14 10:06:53

I guess sqrt decomposition does not work at all.

sarwar__05: 2017-11-24 13:27:36

Segment Tree(range sum) + Offline(sort both array and query) + Faster I/O = AC in 0.38 :D

frozen7: 2017-10-17 10:46:46

BIT + Sorting in descending + Offline + Fast I/O + scanf,printf : AC.. :-)

Last edit: 2017-10-17 10:53:26
a_kk: 2017-10-03 17:07:16

using merge sort tree, how to avoid TLE :(

Last edit: 2017-10-03 17:08:34
rishi_07: 2017-09-28 10:41:55

Learnt something new! Great problem..

stommydx: 2017-09-10 19:31:20

BIT + fast IO still gives TLE :C


Added by:Jimmy
Date:2008-10-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Gomoku