KQUERY - K-query

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/kquery


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 


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

hide comments
2024-08-04 16:24:58
segment tree + upper bound
2023-12-20 14:14:48
similar problem
https://codeforces.com/contest/813/problem/E

Last edit: 2023-12-20 14:15:10
2023-08-04 14:29:40
Merge Sort Tree Classic
2023-07-16 23:46:00
Use MO + BIT, or just MO with sqrt
2023-07-09 11:42:00
I am getting TLE for Merge Sort Tree + Upper Bound Solution
Can someone help please
This is my implementation
<snip>
[Simes]: This is not the place for a code review, use the forum

Last edit: 2023-07-09 19:30:24
2023-05-06 14:10:19
segment tree using merge sort + upper_bound
2023-04-09 18:29:12
segment tree+ binary search
2022-09-17 13:08:53
Uber OA Problem
2022-08-31 11:25:49
nice and easy problem.... merge sort tree + binary search. and boom ;)
2022-06-10 04:39:39
offline segment tree
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.