先离线。区间修改可以被扫描线掉，以下只考虑覆盖当前的修改，其他的当成时间为 -1 即可。
观察特殊性质中的排列随机，一个较为暴力的思路是对一个区间，每次在线段树上二分出下一个覆盖该区间的点并直接切开。
将区间三等分。这样，在左右两段的修改不会导致中段被丢弃。
因此对 $x$ 建线段树，每次问一下第一个在中段的修改，再二分出此修改之前，左段最右的和右段最左的修改，执行这三个修改即可。每次区间长度至少减小 $1/3$。
QOJ.ac
QOJ
The 3rd Universal Cup Finals is coming! Join our Warm-up Game and Prediction Game and win the prizes! Learn more...
Discussion #1551 for Problem #7980. 区间切割
Type: Editorial
Status: Open
Posted by: 3rewnfbjh4fn
Posted at: 2026-04-16 16:36:21
Last updated: 2026-04-16 16:49:58
New Editorial for Problem #7980
Comments
No comments yet.