KQUERY - K-query

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:Duc
Ngày:2008-10-26
Thời gian chạy:0.184s
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:© VNOI

hide comments
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
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!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.