LibreOJ β Round
A. ZQC 的拼图
不同拼图板的顺序是没有影响的，只要把它们的顺序换一下，保持每块拼图板右上角和上一块的右上角相对位移不变即可。
一定存在一个最优解是用了所有的拼图板，并且拼图板的直角顶点在两个方向上都是非递减的。
为了叙述方便，我们设拼图板下边沿为 $x$ 轴，左边沿为 $y$ 轴，左下角为原点 $(0, 0)$，第 $i$ 块拼图板直角顶点为 $(x_i, y_i)$，特别地，规定 $x_0 = y_0 = 0$。
不妨假设
\[\begin{cases} x_i \le x_{i + 1} \\ y_i \le y_{i + 1} \end{cases} \quad i \in [0, n)\]则存在一条从左下到右上的路径的充要条件为
\[\begin{cases} x_n = y_n = m & \\ a_{i + 1} (x_{i + 1} - x_i) + b_{i + 1} (y_{i + 1} - y_i) \le k & \quad 1 \le i \lt n \end{cases}\]这是是一个 $\forall i, f(i) \leq k$ 的形式，可以二分 $k$。
记 $f(i, j, k)$ 表示前 $i$ 块拼图能否到达 $(j, k)$，判定结果为 $f(n, m, m)$。
\[\begin{aligned} f(i, j, k) & = \mathop{\text{or}} \limits_{[f(i - 1, x, y) = 1]} a_i(x_i - x) + b_i (y_i - y) \le k \\ f(i, j, k) & = [a_i x_i + b_i y_i - k \leq \mathop{\max} \limits_{[f(i - 1, x, y) = 1]} a_i x + b_i y] \end{aligned}\]预处理前缀最值，时间复杂度 $\mathcal O(n m ^ 2 \log a)$。
B. ZQC 的树列
若 $k = 2^p$，可以构造一个长度为 $p + 2$ 的递增序列，其中 $a_1, a_{p + 2}$，必选，其余位置可选可不选，子序列个数为 $2^p$。
若 $k = 2^p - 1$，可以构造一个长度为 $p$ 的递增序列，所有位置可选可不选，排除空序列后子序列个数为 $2^p - 1$。
其他情况输出 qnq。
C. ZQC 的截图
使用主席树维护节点到根路径上各颜色的出现次数。
时间复杂度 $\mathcal O(m \log n)$，空间复杂度 $\mathcal O(n + m \log n)$。
D. ZQC 的课堂
$x$ 和 $y$ 的贡献是独立的。
问题转化成维护一个序列 $a$，支持四种操作：
- 指针左移；
- 指针右移；
- 修改指针位置的值；
- 询问有多少个位置 $i$ 满足 $(\sum \limits_{j = 1} ^ i a_j + 1) (\sum\limits_{j = 1} ^ {i - 1} a_j + 1) \lt 0$。
设 $s_i = s_{i - 1} + a_i, s_0 = 1$，即按前 $i$ 个向量移动后的位置。
问题转化成维护一个序列 $s$，支持四种操作：
- 指针左移；
- 指针右移；
- 给指针位置之后的所有数加上某个值；
- 询问有多少个位置 $i$ 满足 $s_i s_{i - 1} \lt 0$。
可以发现 $s_i s_{i - 1} \lt 0$ 等价于 $\max(s_i, s_{i - 1}) \gt 0$ 且 $\min(s_i, s_{i - 1}) \lt 0$，可以容斥求数量，即总数减去 $\max(s_i, s_{i - 1}) \le 0$ 的数目再减去 $\min(s_i, s_{i - 1}) \ge 0$ 的数目。
问题转化成维护两个集合 $\{ \max(s_i, s_{i - 1}) \}$ 和 $\{ \min(s_i, s_{i - 1}) \}$，支持四种操作：
- 插入一个数；
- 删除一个数；
- 给所有数加上某个值；
- 询问不小（大）于 $0$ 的数有多少个。
记录全局偏移量，使用平衡树解决。
时间复杂度 $\mathcal O(q \log n)$。
E. ZQC 的手办
用线段树维护区间最小值及其位置。
用堆查询区间最小的 $x$ 个值，堆中一个四元组 $(l, r, p, v)$ 表示区间 $[l, r]$ 内，$p$ 这个位置的值最小为 $v$，以 $v$ 作为比较的关键字维护一个最小堆。
初始时把整个询问区间的查询结果放入堆中，然后重复以下操作 $x$ 次：
- 取出堆顶元素并加入答案
- 如果 $l \lt p$，把 $[l, p - 1]$ 的查询结果加入堆中
- 如果 $r \gt p$，把 $[p + 1, r]$ 的查询结果加入堆中
- 如果 $v \ge x$ 或区间元素个数不足则答案为 -1。 否则按顺序输出即可。
时间复杂度 $\mathcal O((n + \sum x) \log n)$，空间复杂度 $\mathcal O(n)$。
F. ZQC 的游戏
将所有能被 ZQC 吃掉的食物球质量加入到 ZQC 的质量中,然后从剩余的食物球内标记出能被其他任意一个人吃掉的食物球，设这些球的质量总和为 $s$。
建立网络，对（除 ZQC 外的）每个玩家和每个标记出来的（能被其它人吃掉的）食物球建点。
- 从 $S$ 到每个玩家连边，容量为 ZQC 的质量减去它的质量，表示这个玩家最多还能吃多少；
- 从每个玩家到它能吃到的每个食物球连边，容量为正无穷；
- 从每个食物球到 $T$ 连边，容量为其质量。
若最大流等于 $s$，则方案存在，否则方案不存在。
时间复杂度 $\mathcal O(\mathrm{Maxflow}(n + m, n m))$。
G. ZQC 的作业
计算 $x \in [0, \min(n, \frac{10^8}{\log_2 p})]$ 的结果，用 std::bitset 统计个数。