为什么不 wqs 二分之后直接树形 dp 呢？
by hrgd @ 2022-06-24 21:42:57
因为是单调的，wqs 二分把右边降一降，每次跑 $O(n)$ 的最大权独立集？
by Yahbim @ 2022-06-24 21:44:20
链分治！!1
by hellomath @ 2022-06-24 21:48:46
@[hellomath](/user/20438) az，链分治怎么做?
by Yahbim @ 2022-06-24 22:16:30
@[Yahbim](/user/372708) 由于 DP 数组具有凸性，可以在 $O(\lvert X \rvert + \lvert Y \rvert)$ 的复杂度合并大小为 $\lvert X \rvert, \lvert Y \rvert$ 的 DP 数组
链分治（网上应该有很多资料）意思是，合理规划合并的顺序，使得可以用树剖的复杂度分析合并总代价
by hellomath @ 2022-06-25 18:36:18
@[hellomath](/user/20438) wc，长见识了，有例题么
by Yahbim @ 2022-06-25 20:24:46