猫树分治

猫树分治用于解决合并两区间答案时间为 $O(T)$ 的静态序列问题，时间复杂度为 $O(Tn\log n)$。

实现流程为，对于区间 $[l,r]$，只考虑满足 $l\le L\le \mathrm{mid}<L\le R$ 的询问 $(L,R)$。$O(r-l)$ 处理出 $[\ast ,\mathrm{mid}]$ 和 $(\mathrm{mid},\ast ]$ 的答案，于是就可以对每个询问花 $O(T)$ 合并出答案。最后继续分治 $[l,\mathrm{mid}]$ 和 $(\mathrm{mid},R]$。