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++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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


Comments

Please read the guidelines before commenting.



  • 3
    Huuuuuuh   commented on March 7, 2022, 4:47 p.m.

    Ai cho mình xin test của bài này với


  • 34
    YugiHackerKhongCopCode   commented on Dec. 22, 2021, 4:25 p.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))~