概述
二分查找
二分答案
- 核心思路：把求解性问题变成 naive 的判定性问题。相当于是支付复杂度换可做性。
分数规划
- 考虑化式子，对于 \(mid\)，有
-
其中 \(y_i=0/1\)，表示是否选。当然可能有非 \(01\) 的分数规划...注意到其类似多重背包，至少可以二进制拆分。
-
另外一般会有 \(\sum\limits_{i=1}^n y_i\times w_i\geqslant K\) 的限制，总之不难。
P4377 [USACO18OPEN] Talent Show G
-
题意略。
-
板题，按上面的来就行。check 是一个背包，因为要背够 \(\sum\limits_{i=1}^n y_i\times w_i\)...这么一说，如果是背包 check，显然可以单调队列优化多重。
P4322 [JSOI2016] 最佳团体
- 题意略。就是把上一题的线性 DP 推广到了树形。
P3705[SDOI2017] 新生舞会
-
题意略。是一个二分图最大权匹配的 check...当然我这里用了 SSP。
-
以及，这道题比较卡常（也许是卡 SPFA？），需要调一调参才能确保时间和精度都 OK。
P1642 规划
-
题意略。
-
注意这是一个比较特殊的树形背包；时间很宽裕，直接枚举根做暴力 DP。
整体二分
-
核心思路：迫使每个操作只出现在二分树中的一条链上。
-
把修改（原有的也认为是修改）也视为操作并参与二分。
-
利用值域二分将手上的修改操作变成 \(01\) 操作，然后类似线段树上二分，将询问归到一边。
P3834 【模板】可持久化线段树 2
-
题意：求静态区间第 \(k\) 小。
-
二分答案（二分值域），每次将 \(\leqslant mid\) 的点 \(ins\) 到其下标上，用树状数组维护容易求出区间 \(\leqslant mid\) 的数的个数。
-
足够则询问向左走，否则询问向右走并减去这些数的量。双 \(\log\)，常数较小。
P2617 Dynamic Rankings
-
题意：求动态区间第 \(k\) 小。
-
整体二分完全体的板子。我们借着这道题稍微细讲一下吧：
-
一般的整体二分中，我们二分出当前值域中点 \(mid\) 之后，遍历所有操作，看情况执行（按 \([\leqslant mid]\) 决定权值，也可以说），然后扫所有询问。
-
这其实是隐含着时间关系的：先操作，后询问。那么...当操作与询问有序的时候，自然也可以按这个序来扫。
-
另外应当指出的是，一开始操作是有序的，所以扫完之后还是有序的，没必要排序；只是右区间的操作序列反过来了，故考虑打翻转标记或者对称交换一下。
P3527 [POI2011] MET-Meteors
- 题意略。记得用树状数组+差分实现区间加就好，因为线段树比较卡常。
P1527 [国家集训队] 矩阵乘法
- 题意略。二维树状数组实现一下就好。