I. Ý tưởng

• \(1)\) Có một nhận xét quan trọng là chỉ có \(8\) số hoàn hảo dưới \(3 \times 10^{18}\) là \(\{6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128\}\)
• \(2)\) Khi dựng một cấu trúc dữ liệu, thì tại mỗi vị trí, số sẽ không bị cộng thêm \(1\) quá \(8\) lần, nhưng vì truy vấn \(1\) nên một số có thể bị cộng thêm tối đa \(1\) lần mỗi truy vấn, hay tổng là \(O(q)\).
• \(3)\) Để biết khi nào cần thêm, thì ta kiểm tra xem số có là \(1\) trong \(8\) số hoàn hảo kia không.
• \(4)\) Cách đơn giản để xử lí \((3)\) là tính giá trị nhỏ nhất cần để tới số hoàn hảo tiếp theo, mỗi khi ta cộng giá trị:

  • Nếu một số vượt quá số hoàn hảo (giá trị âm), thì cập nhật lại.
  • Nếu một là một số hoàn hảo (giá trị \(0\)), thì cộng \(1\) và cập nhật lại.
  • Nếu một số chưa tới số hoàn hảo (giá trị dương), thì bỏ qua.

• 5) Thuật toán đơn giản và hiệu quả cho bài toán này là Lazy Segment Tree với truy vấn trên đoạn.

II. Cài đặt

• Ta gọi \(f(x)\) là khoảng cách gần nhất của \(x\) với số hoàn hảo tiếp theo, hay \(f(x) + x\) là số hoản hảo nhỏ nhất lớn hơn hoặc bằng \(x\).

• Ta sẽ dựng cấu trúc dữ liệu Lazy Segment Tree, mỗi nút sẽ quản lý \(5\) thông tin \(\{dist; mini; maxi; assi; addi\}\)

  • \(dist\) chứa giá trị \(f(a_x)\) nhỏ nhất trong các nút lá, hay \(dist = min\left(f(a_x) \ \large|\normalsize\ x = l \rightarrow r\right)\)
  • \(mini\) chứa giá trị \(a_x\) nhỏ nhất trong các nút lá, hay \(mini = min\left(a_x \ \large|\normalsize\ x = l \rightarrow r\right)\)
  • \(maxi\) chứa giá trị \(a_x\) lớn nhất trong các nút lá, hay \(maxi = max\left(a_x \ \large|\normalsize\ x = l \rightarrow r\right)\)
  • \(assi\) chứa giá trị lazy cho truy vấn \(1\) lên nút lá, hay gán \(a_x := assi \ \forall x \in [l, r]\)
  • \(addi\) chứa giá trị lazy cho truy vấn \(2\) lên nút lá, hay gán \(a_x \mathrel{{+}{=}} addi \ \forall x \in [l, r]\)
  • Để đơn giản ta định nghĩa việc phép toán tổng của 2 nút \(a \mathrel{{+}{=}} b\) nghĩa là \(a := \{a_{dist} + b_{dist}; a_{mini} + b_{mini}; a_{maxi} + b_{maxi}; a_{assi} + b_{assi}; a_{addi} + b_{addi}\}\)

• Xét nút \(T\) có \(2\) nút con là \(L\) và \(R\), ta sẽ cập nhật giá trị nút cha trong \(O(1)\) như sau:

  • \(T_{dist} := min(L_{dist}, R_{dist})\)
  • \(T_{mini} := min(L_{mini}, R_{mini})\)
  • \(T_{maxi} := max(L_{maxi}, R_{maxi})\)

• Xét nút \(T\) có \(2\) nút con, không mất tính tổng quát gọi \(U\) là một nút con bất kì, ta sẽ cập nhật lazy nút con trong \(O(1)\) như sau:

  • Trong khi lazy, có giá trị đặc biệt là số \(0\) coi như không cần phải thực hiện cập nhật gì.
  • Khi \(T_{assi} \neq 0\), ta gán \(U := \{f(T_{assi}); T_{assi}; T_{assi}; T_{assi}; 0\}\)
  • Cập nhật \(U \mathrel{{+}{=}} \{-T_{addi}, +T_{addi}; +T_{addi}; 0; +T_{addi}\}\)
  • Nếu \(U_{dist} < 0\) thì ta gán \(U_{dist} := f(U_{mini})\)
  • Cuối cùng ta gán \(T_{assi} := 0\)

• Ta sẽ viết hàm cho truy vấn \(1\), hàm lazy \(assign(l, r, v)\) trong \(O(\log n)\)

  • Tại nút \(T\) chứa đoạn \([p, q] \subset [l, r]\), ta cập nhật \(T := \{f(v), v, v, v, 0\}\)
  • Sau đó ta đẩy lazy xuống nút con
  • Cuối cùng ta cập nhật giá trị nút \(T\) từ \(2\) nút con

• Ta sẽ viết hàm cho truy vấn \(2\), hàm lazy \(additive(l, r, v)\) trong \(O(\log n)\)

  • Tại nút \(T\) chứa đoạn \([p, q] \subset [l, r]\), ta cập nhật \(T \mathrel{{+}{=}} \{-v, +v, +v, 0, +v\}\).
  • Vẫn tại nút \(T\) đó, khi \(T_{dist} < 0\) và \(T_{mini} = T{maxi}\) ta cập nhật \(T_{dist} := f(T_{maxi})\)
  • Sau đó ta đẩy lazy xuống nút con
  • Cuối cùng ta cập nhật giá trị nút \(T\) từ \(2\) nút con

• Ta sẽ viết hàm tính kết quả, hàm \(query(p)\) trong \(O(\log n)\)

  • Với nút lá \(T\) chứa đoạn \([p, p]\), ta trả về \(T_{maxi}\)
  • Ngược lại đi sang nút con trái hoặc nút con phải tùy vào việc vị trí \(p\) nằm trái hay phải của nút cha.

• Tổng độ phức tạp \(O(n + q \log n)\) hoặc \(O((n+q) \log n)\) tùy cách cài:

  • Khi dựng cây chỉ mất \(O(n \log n)\) đến \(O(n)\) tùy cách cài
  • Truy vấn, cập nhật chỉ gọi \(1\) lần mỗi truy vấn và mất \(O(\log n)\)
  • Có tất cả \(q\) truy vấn cần thực hiện