Bình luận

• 
  

  4

  

  nai0610  đã bình luận lúc 11, Tháng 2, 2025, 1:46

  Comment này spoil thuật

  Xử lí truy vấn offline bằng dnc

  Khi đang xử lí đoạn ~[l;r]~ , đặt ~mid=\lfloor \frac{l+r}{2}\rfloor~, gọi ~fl_{i,j}~ là tổng giá trị lớn nhất khi xét các món đồ ở vị trí ~i,i+1,...,mid~ và có tổng ~j~, ~fr_{i,j}~ là tổng giá trị lớn nhất khi xét các món đồ ở vị trí ~mid+1,mid+2,...,i~.

  Tính được ~fl~ và ~fr~ trong ~O(nm)~

  Duy trì các truy vấn hiện tại, khi xét một truy vấn ~(l,r)~ có 3 trường hợp:

  • ~r\leq mid~
  • ~l>mid~
  • ~l\leq mid~ và ~r>mid~ Trường hợp 1,2 khởi tạo thêm 2 tập các truy vấn ~q_l,q_r~ và add tương ứng để xử lí khi gọi đệ quy. Trường hợp 3, kết quả của truy vấn chính là: ~\max_{j=0}^{m} fl_{l,j}+fr_{r,m-j}~

  Độ phức tạp ~O(nlogn)~ theo master theorem.