Submit solution


Points: 0.26 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
© VNOI
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

Please read the guidelines before commenting.



  • 9
    coderbiccubing  commented on July 20, 2023, 7:52 a.m. edit 5

    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!

    Cách xử lý online trên st

    Mỗi nút của cây là 1 vector, với lá là giá trị của nó trong mảng

    Với nút cha, thao tác gộp là merge 2 nút con lại

    Để tìm được số phần tử > k, chỉ cần binary search trên nút

    source code tham khảo: https://ideone.com/4pg51q