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.

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)~

image


Comments

Please read the guidelines before commenting.


There are no comments at the moment.