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++, 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. 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 và cập nhật.
  • ~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.


  • -2
    Huy_inIT  commented on Oct. 10, 2024, 5:11 a.m.

    Có bạn nào làm bằng merge sort tree không, mình xin code đọc với, mình bị tle


  • -21
    khiemgia1105  commented on Oct. 4, 2024, 1:16 p.m.

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


  • -5
    06DinhManhDung  commented on Aug. 2, 2024, 9:24 a.m.

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


  • 51
    trangtrangVN  commented on Feb. 20, 2024, 6:56 a.m. ← edit 38

    K-Query 2 làm như sau:

    * Giải thuật bình thường: Dùng chia căn, chia mảng ra sqrt(n) block.Mỗi block dùng fenwick tree để quản lí.

    • Update: O(log(10000));
    • Trả lời: O(log(10000)*sqrt(n) + sqrt(n))
    • Tổng: O(q(log(10000)sqrt(n) + sqrt(n)))
    • Làm như trên sẽ TLE nên ta dùng segment tree để quản lí các block:

    // Build:

    • build(1,1,sqrt(n)) // Cách build đọc trên wiki vì không có gì đặc biệt
    • Độ phức tạp O(m*log(m)) với m = sqrt(n);

    +// Update:

    • int id = id của block quản lí vị trí update
    • while(id/=2) updateBIT(id,val,-1);
    • val = giá trị mới
    • id = id của block quản lí vị trí update
    • while(id/=2) updateBIT(id,val,1);
    • Độ phức tạp O(log(sqrt(n))*log(10000)) với m = sqrt(n);

    //Get:

    • Viết hàm get như segment tree bình thường (lưu ý xử lí chia căn)
    • Độ phức tạp O(log(sqrt(n))*log(10000)) với m = sqrt(n);
    • Phần updateBIT và getBIT tham khảo bài viết Binary Indexed Tree của vnoi

    //Code tham khảo: (Hãy AC bài trước khi tham khảo)

    https://ideone.com/l8Y2Xb

    • Vậy là sẽ làm được bài này
    • Happy coding!

    • 13
      LA_NHVKhang  commented on Nov. 12, 2024, 1:19 a.m.

      Cảm ơn bạn 🥰


  • -14
    ti21_phnam  commented on Nov. 24, 2022, 3:44 a.m.

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


    • -16
      ti20_ntson  commented on Nov. 24, 2022, 5:10 a.m.

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


      • -8
        2211khanhdh  commented on July 13, 2023, 9:35 a.m.

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


      • -17
        ti21_phnam  commented on Nov. 24, 2022, 8:09 a.m.

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


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

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


  • -65
    chicken_hand  commented on Sept. 2, 2021, 3:13 a.m. ← edited

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