借教室
1、线段树
2、二分+差分
货车运输
1、全局二分
2、边从小到大加入，判两点什么时候连通，倍增求\(LCA\)
运输计划
1、二分路径长，差分求每条边被走过多少次
2、先求\(LCA\)，求其他路径与与最长路径的交
蚯蚓
1、开一个堆
2、开3个队列，第一个放原蚯蚓，第二个放\(p\times x\)的蚯蚓，第三个放\(x-p\times x\)的蚯蚓，易得这个东西单调
天天爱跑步
向上走和向下走分开考虑，可以启发式合并，当然也可以用一个类似差分的东西。
永无乡
启发式合并，可以用\(splay\)写，一个\(log\)。
一个例题
考虑分治，每次找区间最大值，求经过最大值的\(gcd\)之和。因为\(gcd\)最多只有\(\log n\)段，所以枚举\(gcd\)，复杂度\(O(n\log^2n)\)
DSU on Tree
???
考虑一条边在多少个区间里，
原文：https://www.cnblogs.com/zxynothing/p/11624169.html