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
2017-11-05 09:39:22
{kp}
coi chừng giới hạn :"> thân

Last edit: 2017-11-05 09:40:02
2017-10-30 09:23:35
Có ai xử lí online bằng IT+merge Qlog(N)^2 AC không nhỉ.
2017-09-30 04:58:34
Có cái lồn trâu mà AC ấy, bố thử rồi
địt mẹ chúng mày
yasuo vô đối
2016-10-16 10:29:24
Trau cung AC
2016-10-11 02:36:13
bài này mình dùng dp chia căn trên luồng của cây đỏ đen được 97.45 điểmcó pn nào làm vậy không nhỉ
2016-10-06 05:50:27 GYC
trâu cũng ac
2016-08-21 12:55:51 Sơn Tùng M-TP
Giới hạn: 1 ≤ n ≤ 30000, mà để 30003 thì báo sai.
Tăng thêm 1 số 0 mới ac.
Ức chế vãi!
2016-07-15 11:25:52 xin đừng quên tôi
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI: http://yeulaptrinh.pw/287/kquery-spoj/
2016-06-13 16:24:37
Trâu AC ??? Wtf?????????????????????????
2016-06-09 14:04:31
Để integer TLE để hết longint AC =)))
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.