题单地址：https://www.luogu.com.cn/training/1576#problems

动态更新~~

经验之谈

• 找到答案的关键性质。CF1299C
• 或者找到题目的关键性质。CF446B
• 对问题的转化，把它变成一个经典的贪心模型。CF55B
• 神奇的构造方式，按状态建树。CF707D

CF191C Fools and Roads

树上差分随便做。

CF1299C Water Balance

发现答案是单调不降的。

然后维护一个单调栈，栈内的元素包含一段区间的信息，如果上一段区间的平均值大于这一段区间的平均值就将它们合并。

CF446B DZY Loves Modification

你发现行和列之间没有影响。

所以你可以用堆搞出只选行的情况下的前 \(k\) 大，列同理。做一个前缀和存 \(h_i,l_i\) 里。

考虑重合的部分怎么算？假设共选了 \(i\) 行 \(k-i\) 列，那么重合部分为 \(i \times (k-i)\)。

最终答案为 \(\max\{h_i + l_{k-i} - i \times (k-i) \times p\}\)。

CF555B Case of Fugitive

转化一下这个问题，对于所有相邻的两段区间 \([l_{i-1},r_{i-1}]，[l_i,r_i]\)，你发现它需要的线段的长度在 \([l_i - r_{i-1},r_i - l_{i-1}]\) 内，把线段看做点，然后就转化成了多个区间用点覆盖的模型，贪心即可。

CF707D Persistent Bookcase

你发现 \(1,2,3\) 操作都很好做。（是吗？）

对 \(3\) 操作记录一个 \(rev\) 数组，对 \(1,2\) 操作用 \(vis\) 数组记录。

如何处理 \(4\) 操作？

把操作看作点，然后一个操作向下一个操作连边，dfs 即可。

具体来讲，对于 \(4\) 操作，可以加一条 \((k,i)\) 的边，其他操作可以加一条 \((i-1,i)\) 的边。