KQUERY - K-query

no tags 

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 

hide comments
ab_biswas09: 2019-03-18 23:49:20

After So Many TLEs finally AC
Use scanf and printf

vivek_rathi: 2019-03-17 08:07:30

Use scanf and printf otherwise TLE

davidgalehouse: 2019-02-17 02:12:03

Easier than DQUERY in my opinion. Less creativity required in applying the BIT.

abhinav_jain02: 2019-02-01 10:07:19

Try to use BIT instead of segment trees. It works faster and has a smaller code.

a_98: 2018-11-23 14:03:30

BIT does it in 0.17 without fast IO.

yaseenmollik: 2018-11-15 21:35:34

First problem using Offline queries with segment tree :D

phoemur: 2018-10-23 02:08:31

BIT + Offline Query = 0.20s
SegTree + Offline Query = 0.31s
MergeSort Tree + Online Query = TLE

alexandro5432: 2018-10-12 16:09:24

silxikys time limit is 0.184s for each test. Your solution worked in 0.4s for all the tests summed up

silxikys: 2018-08-27 05:31:43

Can be solved using sqrt-decomposition of array and coordinate compression, my sol is 0.4 seconds. Not sure what the 0.184s time limit means.

supriyanta: 2018-08-09 21:56:20

BIT + offline query.
no need to use fast io etc etc.....


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