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.



  • 4
    thinhquoc  commented on April 3, 2024, 1:58 a.m. edited

    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

    Đầu tiên thì chúng ta sắp xếp tăng dần theo mảng k, theo vd sau khi ta sắp xếp ta sẽ có [2,4,1], [1,5,2], [4,4,4]

    Tiếp theo trong cái đoạn từ i->j ta xét xem có phần tử ≤ k không, nếu có ta sẽ xóa phần tử đó(bằng cách gán = 2e9) cho đến khi không còn phần tử nào ≤ k. Vậy ta sẽ có một mảng res[pt]=j-i+1-số phần tử bị xóa(trong đoạn i->j, dùng IT). Cuối cùng là in ra mảng res. Việc tìm vị trí để xóa ta vẫn có thể dùng cây IT.


  • 27
    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