Educational Segment Tree Contest - ITDS1

Xem dạng PDF
Gửi bài giải
Điểm: 0,40
Giới hạn thời gian: 3.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Nguồn bài:
Educational Segment Tree Contest - Anh Nguyên
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 5
    kuriyama_san  đã bình luận lúc 12, Tháng 10, 2024, 10:26

    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  đã bình luận lúc 8, Tháng 10, 2024, 13:46

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


  • -9
    hieudeptrai  đã bình luận lúc 29, Tháng 7, 2024, 3:42

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -8
    Spectrum3563  đã bình luận lúc 5, Tháng 6, 2024, 12:35

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -3
    flechilavt  đã bình luận lúc 2, Tháng 12, 2023, 2:23

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


    • 0
      Huy_inIT  đã bình luận lúc 4, Tháng 10, 2024, 7:29

      merge sort tree


  • -5
    loitran1001  đã bình luận lúc 27, Tháng 11, 2023, 4:41

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -6
      loitran1001  đã bình luận lúc 27, Tháng 11, 2023, 5:08

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 16
    tink29lenhuttri32  đã bình luận lúc 14, Tháng 9, 2023, 2:39

    VanvatthuaFuxuan


    • -5
      anita  đã bình luận lúc 26, Tháng 10, 2023, 12:51

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -8
    Huuuuuuh  đã bình luận lúc 7, Tháng 3, 2022, 9:47

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -18
      vqt  đã bình luận lúc 24, Tháng 7, 2022, 5:48

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 144
    YugiHackerKhongCopCode  đã bình luận lúc 22, Tháng 12, 2021, 9:25

    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))~