2021-计蒜之道-精英组-预赛-第三场-T3-wy的单机游戏
分层图经典问题。

数轴上有 $n$ 个点，坐标分别为 $p_1, p_2, \cdots, p_n$ 在这些点上按照某些规则跳。
规则是：每次向距当前点第 $k$ 小的点跳，如果有相同距离则向下标较小的跳；
求从每个点出发跳了 $m$ 次后在哪里.
$1\leq k < n\leq 10^6, 1\leq m\leq 10^{18}, 1\leq p_i\leq 10^{18}$.

给定 $n$ 个非负整数，选一个子集，使得子集的平均值减去中位数最大。
求这个最大值。

给定一个数列 $a_1, a_2, \cdots, a_n$.
定义在有序数对 $(x, y)$ 上的“好对”：对于 $a_x$，$y\in[1, x)\cup(x, n]$ 能使 $|a_x-a_y|$ 取最小值。
给定 $q\leq 3\times 10^5$ 组询问，每次询问一个区间 $[l, r]$ 中，有多少个好对。
求：每次询问的答案 $Ans_i$ 与询问编号 $i$ 的乘积的和，即：

给定 $n$ 个正整数 $a_1, a_2\cdots, a_n$，求出任意一组 $x\neq y\neq z\neq w$ 使得 $a_x+a_y=a_z+a_w$.
$n\leq 2\times 10^5, 1\leq a_i\leq 2.5\times 10^6$.

给定 $2n$ 个点，其中 $n$ 个在 $x$ 轴上，另外 $n$ 个在 $y$ 轴上。现在要求每一个 $x$ 轴上的点与一个 $y$ 轴上的点连线，每个点恰好被连线一次。求所有线段的欧几里得距离之和。

给定一个长度为 $n$ 的序列，每个元素有权值 $x_i$，现在要将序列分割为若干段，每段中元素连续。设 $s_i$ 表示前缀和，即 $s_i=\sum_{j=1}^{i}{x_j}$，那么对于每段 $[l, r]$，代价为： $$ a(s_{i}-s_{j-1})^2+b(s_i-s_{j-1})+c $$ 其中 $a, b, c$ 为题目给定的常数。整个序列的代价为每段代价之和。
求序列的代价最大值。
$1\leq n\leq 10^6, -5\leq a\leq -1, -{10}^7\leq b, c\leq 10^7, 1\leq x_i\leq 100$.

给定 $n$ 个矩阵的宽 $w$ 和高 $h$，每次选一个矩阵集合，代价为集合中的 $\max{\{w\}}\times \max{\{h\}}$。
任意两次之间没有重复的矩阵，求取完所有矩阵的最小代价。