2021.09.25模拟赛

最是人间留不住，朱颜辞镜花辞树

诡异的翻译

~~有梦想你也45~~

考虑每个点如果减去了 $c(x)$

那么有 $p(u)-c(u)+p(v)-c(v)=w(u,v)$

即 $c(u)+c(v) = p(u)+p(v)-w(u,v) $

右边是个定值，根据之前某个题的思路，如果一个联通块里钦点了一个点 $x$ 确定了，别的点 $y$ 就可以表达成 $\pm c(x)+B_y$

dfs 搜一下搜出来符号和 $B_y$ 碰到已经访问的点就联立解下方程判有无解

总和是 $c(x) \times \sum K_y+\sum B_y$

更新点的时候顺便更新下最小/大值带入即可

二维数点可以考虑 CDQ

考虑按 $y$ 坐标排序，按 mid 分成两个部分，然后分别按 $x$ 排序，钦点上边的一个点作为右上角

他能贡献到的点是在下半部分的一段单调递减的序列，单调递减可以用一个单调栈去维护

$y$ 的显示保证了，需要考虑 $x$ 的限制，能够贡献的区间是离他最近的 $y$ 小于它的点

也用一个单调栈维护，然后再第一个单调栈上二分即可

显然的贪心，小的 $a$ 匹配小的 $b$ 即可

贪心的考虑，我们希望先满足每个菜 $k$ 个人的条件

那么让每个人贡献一个 $1$ 的时间给所有菜，那一个人这方面的贡献是 $\min(n,b_i)$

要合法的化就要满足选取的人的 $\sum b_i \ge \sum a_i$

且贡献到 $k$ 个时间 $\ge nk$

背包跑一下就行