Editorial for Bảng
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Ta sử dụng sparse table 2 chiều:
Gọi ~f_{i,j,k}~ là ô vuông góc trên trái là ~(i,j)~, mở rộng về bên phải và bên dưới ~2^k~ ô. Khi đó:
- ~f_{i,j,k} = max(f_{i,j,k-1}, f_{i+2^{k-1},j,k-1}, f_{i, j+2^{k-1},k-1}, f_{i+2^{k-1}, j+2^{k-1}, k-1})~
Để cyclic shift bảng thì ta nhân đôi bảng về cả 2 phía. mỗi lần shift ~(u,v)~ thì ta sẽ chỉnh góc trên trái thành ~((x+u)\; mod \; n, (y+v)\; mod \; n)~
Comments