Editorial for Bedao Regular Contest 06 - PYRAMID2


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.

Author: bedao

Ta quan sát thấy được quy luật của kim tự tháp ~(m, n)~ là số ~1~ sẽ được lặp lại ~n + 1~ lần, số ~m~ sẽ lặp lại ~n~ lần, và các số trong khoảng từ ~[2...m - 1]~ sẽ lặp lại ~2n~ lần:

~(n + 1) + \sum\limits_{i=2}^{m - 1} i \times 2n + m \times n~

= ~(n + 1) + (m - 2) \times (m + 1) \times n + m \times n~

= ~1 + n \times (m^2 - m - 2 + m + 1)~

= ~1 + n \times (m^2 - 1)~

Như vậy với công thức trên ta có thể trả lời mỗi truy vấn trong ~O(1)~.

Độ phức tạp: ~O(q)~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.