wqs 二分

· · 个人记录

据说 wqs 的论文是在 2012 年，但我手上的论文集 2012 年是命题答辩，没有这篇，求 PDF

wqs二分 学习笔记

又称带权二分，DP 凸优化

LC188 Best Time to Buy and Sell Stock IV

CF125E MST Company

给出 Tree I 的构造方式

wqs 二分时按最多白边的策略做 MST。二分结束后按最少白边策略做 Kruskal，同时可以得到哪些白边是必选的，先把这些边连上。再按最多白边策略做 Kruskal，同时可以得到 mx[i] 表示考虑完了边权 \le i 的边，之后最多加入多少条白边到 MST 中
构造方案时一起考虑边权为 w 的边，先加入白边至 cnt+mx[i]=need，剩下的全部加黑边即可
在上述过程中加入对无解的判断是平凡的

code

CF739E Gosha is hunting

嵌套 wqs 二分是假的，新做法：

每个位置独立，凸性显然

先假设每个位置不用 A 球（B 球可取可不取），贡献为 $\max(u_{i}-mid,0)$。若用 A 球，增量为 $\max(p_{i},p_{i}+u_{i}-p_{i}u_{i}-mid)-\max(u_{i}-mid,0)$，排序后取前 $a$ 大的即可。为了计算使用 B 球的数量，还需要记录每个位置采取的决策 ### [LG6246 [IOI2000] 邮局 加强版](https://www.luogu.com.cn/problem/P6246)