- 搬题人
- 饼干：Wu_Ren
- 消愁：hehezhou
- 养鸡：flower
- 组题人：p_b_p_b
- 题解：别急，别急，flower
饼干
来源：
- Petrozavodsk Summer 2020 Day 5: JAG Summer 2019+, Problem L
- https://qoj.ac/contest/505/problem/1346
Tutorial by Wu_Ren.
考虑如果仍然需要补魔，那么先施法再补魔一定比先补魔再施法更劣。
那么我们每次一定是，先施法然后补满，直到某次我们施法完之后，把魔补到剩下消耗的总和，然后依次施完。
那么这个过程就相当于我们每个魔咒变成 $a_i$ 个物品，第 $j$ 个物品权值是 $j$，然后我们有 $m$ 次机会把某个魔咒里权值最小的那个物品删去，我们称这个为操作一。
我们要求最后权值和最小。
然后吃饼干就是有 $k$ 次机会把某个魔咒里权值最大的那个物品删去，我们称这个为操作二。
仔细分析一下，我们就是每次对最大的 $a_i$，使用 $a_i$ 次操作一（不足就全用了）。等所有操作一用完后，贪心地使用操作二即可。
复杂度 $O(n\log n+m)$ 或 $O(n\log n)$。
消愁
来源：
- Petrozavodsk Summer 2021 Day 3: GP of IMO, Problem J
- https://qoj.ac/contest/693/problem/1839
别急
养鸡
来源：
- Petrozavodsk Summer 2022. Day 7. HSE Koresha Contest, Problem A
- https://qoj.ac/contest/1016/problem/4878
Tutorial by flower.
显然是个二分图最大流的模型，接下来用用流的语言的来描述问题。
首先有个贪心做法。每次从 $n$ 扫到 $1$ 遇到一个区间的 $r$ 就加入这个区间，然后对于每个点尽量流 $l$ 最大的。
当 $l, r$ 递增的时候。可以发现上述贪心做的事情是，先加入的区间尽量先流，与 $l$ 具体啥样无关。如果从$n$担心到$p$，再从 $1$ 贪心到$p-1$。两侧的用到的区间是一个前缀和一个后缀。如果总和不爆那就不会冲突，也就是说答案是 $\min(lmaxflow + rmaxflow, \sum_{l_i \le p \le r_i} f_i)$。其中 $f$ 是区间的流量
计算 $rmaxflow$ 可以用 hall 定理，令 $s_i = \sum_{l_j \le p \le r_j \le i} f_j - \sum_{j = p}^{i} a_p $，其中 $a$ 是右侧一个点的流量。
那么答案就是所有区间流量和减去 $\max s_i$，用线段树维护即可。
考虑贪心在做的事情是保证右侧为最大流的情况下，尽量的选 $l$ 最大的，只要我们求出了每个点右侧的情况，那么把每个区间的剩余流量扔左侧跑个最大流即可。
考虑一个 $s_i$ 的含义是：$p$ 到 $i$里至少要浪费 $s_i$ 的区间的流量扔到左侧。把$s$的前缀最大值位置拎出来是 $i_1, i_2, \cdots, i_k$。
考虑 $p$ 到$i_k$ 里优先级最小（$l$ 最小）的区间假设在位置 $x$。令 $i_t \le x$ 且$t$最大，那么这个前缀要浪费$s_{i_t}$而总共要浪费$s_{i_k}$，那么就直接给这个区间的左侧部分增加 $\min(f, s_{i_k} - s_{i_t})$ 的流量，因为这些一定是被浪费的。
考虑直接线段树暴力维护上述过程，下面证明操作次数不超过$O(n\log n)$。
需要对于$s$ 数组做的事情是后缀加和把最大值和降低为非严格最大值。
考虑在线段树的结构，势能为有多少个节点的区间最大值来自右子树（如果相等认为在左子树）
那么每次操作都会使得使能少$1$（$i_k$, $i_t$ 在线段树的 lca），后缀加只会影响$\log n$个区间的相对顺序。 算上线段树操作的时间复杂度是 $O(n\log^2 n)$。
