K-query
View as PDF
Submit solution
Points:
0.26 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
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
Comments
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!