Educational Segment Tree Contest - ITDS1

View as PDF
Submit solution
Points: 0.40
Time limit: 3.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem source:
Educational Segment Tree Contest - Anh Nguyên
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

In case the statement didn't load correctly, you can download the statement here: Statement

Comments

Please read the guidelines before commenting.


  • 4
    kuriyama_san  commented on Oct. 12, 2024, 10:26 a.m.

    Các bạn có thể xem hướng dẫn chi tiết trên Wiki của VNOI, rất dễ hiểu và dễ cài đặt: https://wiki.vnoi.info/algo/data-structures/segment-tree-basic.md ví dụ 3


  • 0
    khai05  commented on Oct. 8, 2024, 1:46 p.m.

    Thay multiset thành map nó chạy max 2,5s :))


  • -8
    hieudeptrai  commented on July 29, 2024, 3:42 a.m.

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


  • -7
    Spectrum3563  commented on June 5, 2024, 12:35 p.m.

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


  • -3
    flechilavt  commented on Dec. 2, 2023, 2:23 a.m.

    này làm sao viết hàm build v mn


    • 0
      Huy_inIT  commented on Oct. 4, 2024, 7:29 a.m.

      merge sort tree


  • -5
    loitran1001  commented on Nov. 27, 2023, 4:41 a.m.

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


    • -5
      loitran1001  commented on Nov. 27, 2023, 5:08 a.m.

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


  • 17
    tink29lenhuttri32  commented on Sept. 14, 2023, 2:39 a.m.

    VanvatthuaFuxuan


    • -4
      anita  commented on Oct. 26, 2023, 12:51 p.m.

      vanvatthuaOtto


  • -7
    Huuuuuuh  commented on March 7, 2022, 9:47 a.m.

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


    • -17
      vqt  commented on July 24, 2022, 5:48 a.m.

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


  • 141
    YugiHackerKhongCopCode  commented on Dec. 22, 2021, 9:25 a.m.

    Cmt này spoil thuật!

    Thuật 1: IT

    Mỗi node là 1 set/multiset

    Truy vấn update

    Khi đoạn cần update có ~l==r~ thì ta xóa số ~a[i]~ cũ và thêm ~v~ vào multiset

    Trường hợp ~l~ != ~r~ thì ta kiểm tra cây con trái hay cây con phải vừa bị xóa số, ta xóa số đó đi và thêm v vào multiset

    Ngoài ra còn có cách đơn giản hơn là khi ~l==r~ thì tất cả các đoạn chứa ~a[i]~ sẽ đều phải xóa 1 giá trị ~a[i]~ và thêm 1 giá trị ~v~, ta sẽ dùng 1 vòng while chạy ngược về để update.

    Truy vấn get

    Tìm số nhỏ nhất ~\geq k~ trong đoạn từ ~l~ đến ~r~ và return

    Độ phức tạp:

    Bộ nhớ: ~N.log(N)~ (vì độ sâu tối đa là log(N)).

    Thời gian: ~N.log(N)^2~ (thời gian tìm kiếm trên set là ~logN~).

    Thuật 2: Chia căn

    Đặt block = ~sqrt(N)~

    Mỗi đoạn độ dài block ta sẽ cho vào 1 multiset

    Truy vấn update

    Xóa ~a[i]~ cũ trong block chứa ~i~, thêm ~a[i]~ mới vào.

    Truy vấn get

    Tìm trong đoạn từ ~l~ đến ~r~ có bao nhiêu block hoàn chỉnh và get trong các block đó, còn phần dư 2 bên thì duyệt trâu.

    Độ phức tạp:

    Bộ nhớ: ~N~

    Thời gian: ~N + M.sqrt(N).log(sqrt(N))~