三分等价于二分斜率。
因此完全可以求导后直接做二分。
整体二分
分治,对多个个体同时做二分。
考虑对单个星球二分。则基础想法是以时间为线段树下标,在主席树中二分。
考虑拓展到整体二分。则基础想法是二分时间,试着加入陨石雨。可以用树状数组做到 \(O(n \log^2 n)\),也有差分 + 离散化 \(O(n \log n)\)。
分治
主要思想大概是把大问题分成小问题再合并起来。
所以一般要求问题有可分性, 同时有可合并性。
排序解决 \(a_i\),归并解决 \(b_i\),树状数组解决 \(c_i\)。
标签:二分,log,树状,分治,基础,网课,优化,技巧 From: https://www.cnblogs.com/David-Mercury/p/18342631