本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-18 16:23:04

:::::info[题目基本信息] 考察：Ad-hoc（省选/NOI-）。
题目简介：
给定 $n$ 个序列，第 $i$ 个序列为 $\{a_{len_i}\}$，现在在这 $n$ 个序列各选 $1$ 个数，问所选数字和前 $k$ 小选法的所选数字总和是多少。
数据范围：

• $1\le n,k\le 10^5$
• $\forall i\in[1,n],1\le len_i\le 10$
• $\forall i\in[1,n],j\in[1,len_i],1\le a_{i,j}\le 10^8$

时间限制：1s 至 3s。
空间限制：250MB。
::::: 首先我们可以想到通过一个 $n$ 元组记录一个状态，使用堆可以做到 $\Theta(nk\log nk)$，显然过不了。我们考虑优化。
我们考虑一行一行扩展，这时容易发现若设目前处理的行为 $x$，则前 $x-1$ 行的具体情况并不重要，$x+1$ 行及以后都是 $1$，所以容易设三元组 $(x,y,w)$ 表示处理到第 $x$ 行，同时第 $x$ 行扩展到了第 $y$ 列，同时当前数字和为 $w$，容易扩展：

• 扩展到下一列（前提为 $y\ne len_x$），同时令 $y\leftarrow y+1,w\leftarrow w-a_{x,y}+a_{x,y+1}$。
• 跳到下一行（前提为 $x\ne n$），令 $x\leftarrow x+1$。

但是这样还是不行，每次扩展会直接跳到最后一行，相当于多了 $\Theta(nk)$ 个状态，时间复杂度是 $\Theta(nk\log k)$ 的。
所以我们考虑把跳行这一步省略掉，只在扩展后跳行，这样我们扩展时也能一步扩展，画出来就是这样的一棵递归树（为了清晰，我们以 $\{len_n\}=\{3,2,3\}$ 为例，同时下图的三位数表示最开始的 $n$ 元组）：
这是一棵多叉树，叉数最多能达到 $\Theta(nV)$（其中 $V$ 是 $\{len_n\}$ 的值域）级别，如果我们直接这样做能做到 $\Theta(nkV\log nV)$，还是很慢（怎么更慢了），继续优化。
现在我们唯一的需求就是减少叉数，我们想到可以左儿子右兄弟表示法，更改一下是这样的：

这时就有了一些状态转移方式，为了方便统一，我们把类似 $311\rightarrow 121$ 的边变成 $211\rightarrow 121$，然后再次将状态转化为 $(x,y,w)$，容易发现有 $3$ 种边：

1. $211\rightarrow 311$ 等：即 $(1,2,w)\rightarrow(1,3,w)$，扩展一次（前提条件为 $y\ne len_x$），即同时令 $y\leftarrow y+1,w\leftarrow w-a_{x,y}+a_{x,y+1}$。
2. $211\rightarrow 221$ 等：即 $(1,2,w)\rightarrow(2,2,w)$，跑到下一行扩展一次（前提条件为 $x\ne n$ 且 $y\ne 1$，通过观察递归树容易发现这一行必须扩展了），即同时令 $x\leftarrow x+1,y\leftarrow 2,w\leftarrow w-a_{x+1,1}+a_{x+1,2}$。
3. $211\rightarrow 121$ 等：即 $(1,2,w)\rightarrow(2,2,w)$，撤销一次并跑到下一行扩展一次（前提条件为 $x\ne n$ 且 $y=2$），即同时令 $x\leftarrow x+1,y\leftarrow 2,w\leftarrow w-a_{x,2}+a_{x,1}+a_{x+1,2}-a_{x+1,1}$。

然后我们就做完了这道题，但是还有若干细节。
:::::warning[细节]

1. 为了保证优先队列求第 $k$ 小的正确性，我们要保证后面出现的值不小于前面出现的值，具体地：
   • 对于每个数列，将其从小到大排序。
   • 对于这 $n$ 个数列，将它们按照 $a_{i,2}-a_{i,1}$ 从小到大排序。
2. 上面的扩展方式只适用于 $len_i\ne 1$，对于 $len_i=1$，我们要手动计算答案并把它剔除。
   ::::: 时间复杂度为 $\Theta(k\log k+nV)$，空间复杂度为 $\Theta(nV)$。

code