K-query II

View as PDF

Submit solution

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

Problem source:
© VNOI
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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. Ngoài ra còn có một số thao tác cập nhật.

Một thao tác cập nhật là một cặp (~i~, ~v~) nghĩa là ~a_{i}~ cần được gán giá trị ~v~.

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^{4}~).
  • Dòng ~3~: ~q~ (~1~ ~\leq~ ~q~ ~\leq~ ~200000~), số truy vấn-k.
  • ~q~ dòng tiếp theo, số đầu tiên trong mỗi dòng là ~0~ hoặc ~1~. Số ~0~ theo sau bởi ~2~ số ~i~ và ~v~ (~1~ ~\leq~ ~i~ ~\leq~ ~n~, ~1~ ~\leq~ ~v~ ~\leq~ ~10^{4}~) cho biết một thao tác cập nhật. Số ~1~ theo sau bởi ~3~ số nguyên ~i~, ~j~, ~k~ (~1~ ~\leq~ ~i~ ~\leq~ ~j~ ~\leq~ ~n~, ~1~ ~\leq~ ~k~ ~\leq~ ~10^{4}~) cho biết một truy vấn-k.

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
6
1 2 4 1
0 4 10
1 4 4 4
0 3 1
0 1 2
1 1 5 2

Sample Output

2
1
2

Comments

Please read the guidelines before commenting.



  • -4
    ti21_phnam   commented on Nov. 24, 2022, 10:44 a.m.

    Nếu bài này truy vấn i = 0 là dạng tăng mỗi phần tử trên đoạn [l,r] lên x thì làm như thê nào vậy ạ.


    • -3
      ti20_ntson   commented on Nov. 24, 2022, 12:10 p.m.

      Bạn có thể xử lí bài này bằng chia căn


      • -1
        ti21_phnam   commented on Nov. 24, 2022, 3:09 p.m.

        Bạn có thể giảng chi tiết hơn được không ạ. Mình cảm ơn ạ.


  • -8
    khanhtuanitk20   commented on Dec. 25, 2021, 11:11 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -33
    chicken_hand   commented on Sept. 2, 2021, 10:13 a.m. edited

    This comment is hidden due to too much negative feedback. Show it anyway.