2023.9.1 AT practise

ARC072F

设“热量”为 \(T_1V_1+T_2V_2+...\)，最后要求的温度就是 \(\dfrac{T_1V_1+T_2V_2+...}{V_1+V_2+...}\)，
由于最后体积是恒定的，那么我们只需要解决热量的问题即可。

设 \(f_{i,x}\) 表示第 \(i\) 天晚上只能留下 \(x\) 升水的最大热量。
如果我们把写成函数 \(f_i(x)\)，我们发现其一定是上凸的函数。
因为我们有这样一个策略：
若加入的水温度高，那么我们肯定不想让其跟热量低的水混合。（斜率大）
若加入的水温度低，那么我们肯定想让其跟热量高的水混合。（斜率低）
那么我们可以维护凸壳。

每天加水的操作就是相当于在底部加了一个矢量，然后处理一下这个凸壳。

图片中原点跟某个点连线取 \(\max\)，其实就是混合的操作。
大抵是如此，我们用单调队列维护凸壳即可。

ARC073F

首先有一个浅显的做法：\(f_{i,j}\) 表示完成第 \(i\) 个要求，其中一个人在 \(a_i\)，一个人在 \(j\)，的最小代价。
转移是 \(f_{i,j}\leftarrow f_{i-1,j}+|a_i-a_{i-1}|\)
\(f_{i,a_{i-1}}\leftarrow \min(f_{i-1,j}+|j-a_i|)\)

如果把每个 \(f_i\) 扔到线段树上维护呢？
我们发现第一个转移就是全局加，打一个 tag 即可。
第二个转移如何操作呢？首先先把绝对值拆开，
对于 \(j\le a_i\) 的，贡献是 \(f_{i-1,j}-j+a_i\).
对于 \(j>a_i\) 的，贡献是 \(f_{i-1,j}+j-a_i\).
那么我们分别维护 \(f_j-j,f_j+j\) 的最小值即可，区间查询。

枚举 \(i\) 的同时，顺便更新线段树就行了的。