大概形如每次给定一个区间 \([L,R]\)，每对 \(L\le u<v\le R\) 的 \((u,v)\) 会有一个贡献，要求所有点对的贡献（取min/max，数颜色等）。
考虑点对共有 \(O(n^2)\) 个，遍历一遍所有对也会超时。考虑删除一些无用的点对（例如包含的区间里面有比它更优的），那不看它也会有贡献。如果能证明有用的点对个数较小那就可以扫描线来做。
比如：P7880 [Ynoi2006] rldcot
还是枚举 \(LCA\)，对于 \(x\)，通过启发式合并可以找出所有 \(LCA(i,j)=x\) 的点对。总点对有 \(n^2\) 个。但观察到对于 \(i\)，只用和它的前驱/后继配对就可以。于是有用的点对只有 \(\Theta(n\log n)\) 个，求下来大力扫描线即可。
标签：题目,贡献,有用,扫描线,LCA,区间,一类 From： https://www.cnblogs.com/wwlwakioi/p/17498461.html