---
# System prepended metadata

title: Bedao propose 2022/11/30 solution

---

# Bedao propose 2022/11/30 solution

Sol:
Dựng cây IT, mỗi nút lưu lại một vector độ dài $k+1$, trong đó IT[i][j] là giá trị của $g(l,r)$ khi $k = j$. Các thao tác sẽ tốn $log_n \times k^2$