Comments

• 
  

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