由于只需要求最大值，而题目的操作并不改变数的相对大小关系，因此可以直接维护线段树区间最大值。RESTORE 操作可以直接打标记。标记形如 $x\mapsto ((x\text{ or }x_{init}) + add)/div$。这样有可能超过 int 范围，可以改成 $x\mapsto x/div+[x\bmod div\ge threshold]+add$。时间复杂度 $O(N+Q\log 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 #301 for Problem #11629. ADD, DIV, MAX
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-14 06:58:04
Last updated: 2025-12-14 06:58:09
题解
Comments
No comments yet.