K-query
Xem dạng PDF
Gửi bài giải
Điểm:
0,26 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho một dãy ~n~ phần tử ~a_{1}~, ~a_{2}~, ..., ~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~ ~\leq~ ~i~ ~\leq~ ~j~ ~\leq~ ~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}~.
Input
- Dòng ~1~: ~n~ (~1~ ~\leq~ ~n~ ~\leq~ ~30000~).
- Dòng ~2~: ~n~ số ~a_{1}~, ~a_{2}~, ..., ~a_{n}~ (~1~ ~\leq~ ~a_{i}~ ~\leq~ ~10^{9}~).
- Dòng ~3~: ~q~ (~1~ ~\leq~ ~q~ ~\leq~ ~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~ ~\leq~ ~i~ ~\leq~ ~j~ ~\leq~ ~n~, ~1~ ~\leq~ ~k~ ~\leq~ ~10^{9}~).
Output
- 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.
Sample Input
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2
Sample Output
2
0
3
Bình luận
Vì sự cố bàn phím ngoài ý muốn nhưng để bình luận không trở nên vô ích thì sẽ hướng dẫn làm bài này bằng xử lý offine, không hay hoặc hay thì bạn có thể downvote
bài này đã có hướng dẫn trên VNOI Wiki, link cho ae tham khảo: https://vnoi.info/wiki/algo/data-structures/segment-tree-extend.md
cmt sau đây spoil thuật cho ae nào lười đọc!