注意到 $l_p$ 的和只有 $O(n^2)$，并且 power 的函数关于 $w_p$ 是线性的，因此我们只需要对每个 $l< n$ 保留最大和最小的 $w_p\pod{l_p=l}$，而 $l_p\ge n$ 的文明个数是 $O(n)$ 的，可以暴力枚举。
每个询问中修改的值的个数是 $O(1)$ 的，暴力维护即可。
时间复杂度 $O((n+q)\cdot n)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #185 for Problem #859. Civilizations
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-12 23:58:30
Last updated: 2025-12-12 23:58:36
题解
Comments
No comments yet.