题解2

思路

暴力做法：枚举区间求LCA。

优化：考虑快速计算合并LCA相同的区间。

枚举右端点 $r$ ，维护所有左端点 $i$ 对应的 $[i,r]$ 区间LCA，显然所有以 $r$ 为右端点的区间的LCA在根节点到 $r$ 的链上，且 $i$ 越小，LCA越浅。

使用单调栈按深度递增维护对应所有左端点的LCA，合并所有LCA相同的左端点，所有贡献即可维护。

复杂度

$O(nlogn)$

代码

略