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 


Được gửi lên bởi:Jimmy
Ngày:2008-10-26
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Gomoku

hide comments
2018-11-18 11:45:29
mất 1 đấm vì giới hạn, mất 1 đấm vì cin cout, phải đến phát thứ ba mới AC :///
2018-11-07 02:40:31
offline mới AC -_-
cda.dev
2018-11-01 02:55:01
Dùng BIT là AC hehe
CYB

Last edit: 2018-11-01 03:21:36
2018-11-01 02:44:28
Used Fenwick Tree AC
2018-09-08 05:26:00
Merge sort tree không AC? Any idea with online processing?

Edit: Merge sort tree AC với fractional cascading (online)

Last edit: 2018-09-08 06:15:08
2018-08-26 16:11:28
chục đấm vì xài cin cout :)
2018-08-18 19:35:41
tao ac với time 0.38s :D
2018-01-07 10:34:20
Gần chục đấm AC :V
giới hạn N <= 3*10^5
frostpixel aka.How 2 AC
2017-12-03 01:46:05
nhật hào sạch
2017-11-27 05:10:56
cẩn thận giới hạn
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.