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.


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


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

    bài này cài multiset nhưng vẫn hơn 3s vậy mn có cách nào giảm được thời gian không?


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

      chỉnh sửa: Đã AC, game này nhân phẩm


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

    VanvatthuaFuxuan


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

      vanvatthuaOtto


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


    • -14
      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.


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