Bình luận

• 
  

  11

  

  hieuhfgr  đã bình luận lúc 16, Tháng 9, 2024, 4:00

  Mô sai (my sol)

  Hints:

  Segment Tree với mỗi node mang giá trị ~sum~, ~cnt~ tượng trưng cho tổng phần tử và số lượng phần tử chưa xóa khi xét node đó. Hợp nhất hai nút kiểu sao (toán)

  Làm sao để tìm ra vị trí ban đầu khi cho vị trí sau khi xóa?

  Solution:

  Ta có cây Segment Tree với cách gọi nút như ở trên, và ta có mảng ~pw_i~ tượng trưng cho ~2^i~

  Khởi tạo build:

  • ~(l == r) \to st[id] = (a[i]-'0', 1)~

  Hợp nhất hai nút:

  • ~st[id].sum = (st[id*2].sum*pw[st[id*2+1].cnt] + st[id*2+1].sum) %MOD~
  • ~st[id].cnt = (st[id*2].cnt + st[id*2+1].cnt) %MOD~

  Vậy với mỗi truy vấn ta chỉ cần quay về vị trí ban đầu và get hoặc update như bình thường.

  Ý tưởng của mình về việc xử lí vị trí (Fenwick Tree + Chặt Nhị Phân):

  • Ban đầu, với mỗi vị trí ~i~ thì ta lưu tổng từ ~1 \to i~. Vậy thì nếu xóa ~1~ chỉ số thì từ chỉ số cũ về sau sẽ bị giảm đi ~1~ đơn vị. Ta có thể chặt nhị phân tìm vị trí ~i~ nhỏ nhất thỏa mãn tổng từ ~1 \to i~ = ~p~

  lần 5 viết sol mong mọi ng đừng downvote T_T

• 
  

  5

  

  chunguyen2k8  đã bình luận lúc 18, Tháng 3, 2024, 7:06

  1007050321 là số nguyên tố ae nhá