English

Vietnamese

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ử a₁, a₂, ..., a_n 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 a_i, a_i+1, ..., a_j.

Dữ liệu

• Dòng 1: n (1 ≤ n ≤ 30000).
• Dòng 2: n số a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).
• 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 ≤ 10⁹).

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 a_i, a_i+1, ..., a_j 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

< Previous 1 2 3 Next >
	joysaha: 2024-08-04 16:24:58 segment tree + upper bound
	narutoumania: 2023-12-20 14:14:48 similar problem https://codeforces.com/contest/813/problem/E Last edit: 2023-12-20 14:15:10
	abhi_8: 2023-08-04 14:29:40 Merge Sort Tree Classic
	thegamercoder: 2023-07-16 23:46:00 Use MO + BIT, or just MO with sqrt
	vigneshwaran_: 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
	acrafi: 2023-05-06 14:10:19 segment tree using merge sort + upper_bound
	optimus965: 2023-04-09 18:29:12 segment tree+ binary search
	dhaka_1436: 2022-09-17 13:08:53 Uber OA Problem
	fuadul_hasan: 2022-08-31 11:25:49 nice and easy problem.... merge sort tree + binary search. and boom ;)
	olympia11111: 2022-06-10 04:39:39 offline segment tree