给定数组 $a_i$，定义 $f(i,j)=|\sum_{p=i}^j a_p|$，称数组的美丽度为 $\max\{f(i,j)\}(i\le j)$。每次给定一个 $x$，$m$ 次询问，每次询问在将整个数组加上 $x$ 的基础上的美丽度。询问相互独立。
$n\le 2\times 10^5$。

给出 $n$ 个物品，每个物品有一个权值 $w_i$。
定义一个集合 $S$ 的权值为 $W(S)=|S|\sum_{x\in S} w_x$，对于一个集合的划分，定义其权值为 $W'(R)=\sum_{S\in R} W(S)$。
求所有将 $n$ 个物品分为 $k$ 个集合的方案的权值和。
$n,k \le 2\times 10^5,w_i \le 10^9$

开始手上有数字 $0$ ，每秒按照一定概率选择一个 $[0,2^n-1]$ 之内的数字，将手上的数字或上他。问手上的数变成 $2^n-1$ 的期望秒数。
$n\le 20$，满足 $\sum p_i = 1$

在一条长度为 $B$ 的线段 $l$ 上，等距离截取一些点（包括左右端点），令点数为 $n$，相邻两个端点间距离为 $d\ (d \le D)$。每个端点处都作一条长度为 $H$ 的线段垂直于 $l$。相邻线段之间都存在一条全等的抛物线，抛物线总长为 $L$，令其最低点与 $l$ 的距离为 $h$。给定 $D,H,B,L$，求在 $n$ 最小时 $h$ 的值。
满足 $B \le L$

给定一棵 $n$ 个点，以 $1$ 为根的树，现让你对边染色 $(0/1)$ 。有 $m$ 条限制，每条限制形如 $(u_i,v_i)$ ，意为 $u_i$ 到 $v_i$ 的路径上至少要有一条 $1$ 边，其中保证 $u_i$ 是 $v_i$ 的祖先。问染色方案数。
$n,m \le 5 \times 10^5$