还不回来吗 - 洛谷保存站

个人感觉这题更像一个构造题。听说这个构造很典？反正我赛时没想出来。

我们大家肯定都做过一道题叫做[序列合并](https://www.luogu.com.cn/problem/P1631)。这道题就是把那题拓展到数列个数很大的加强版。

如果没做的话，建议做了这题之后再来写这题。如果做了，建议回去看一下那题的做法，因为我是直接基于那题解法继续写的。

首先不难想到一个暴力思路是，直接把原来削弱版的结论暴力推广，这样复杂度就是 $O(n^n\sum_{i=1}^na_i)$，$a_i$ 是数列 $i$ 的元素个数。

然后说一个与正解无关的优化方法（不看不影响理解正解做法）。就是我们可以把每次比较进行优化。一次操作相当于将 $n$ 个元素中的某一个 $+1$ 然后放入原优先队列中，那么我们可以把这个 $n$ 元组写个双哈希存起来，然后预处理哈希值，修改过程是 $O(\log n)$ 的（因为找到这个元素的前驱后继是经典的哈希上二分的套路）。这样复杂度就是 $O(n\log n\sum_{i=1}^na_i)$ 的了。

不过我赛时因为数组开太大了爆空间然后寄了。

然后我们考虑进一步优化。我们发现这个原先暴力（我指的是 $O(n^n\sum_{i=1}^na_i)$ 的暴力方法）的主要瓶颈在于，你会枚举出很多重复的元素。

举个例子，就比如说我现在有两个方案：

```
1 1 2  -->  1 2 2

1 2 1  -->  1 2 2

```

我们发现两个不同的数列 $\{1,1,2\}$ 和 $\{1,2,1\}$ 拓展后出现了一个完全相同的数列 $\{1,2,2\}$。你可能觉得这个东西几百次才重复一次啊，但是这个重复的频率实际上是很高的，如果每次都判重肯定会带来极高的复杂度。

因此，我们的优化目的是：能否找到一种方案，使得每个不同的数列拓展不会产生相同的一个数列。

那么，接下来请**欣赏**这个解法（说“欣赏”的原因是因为如果你没做过这个套路是真的很难想到的）：

首先，我们按次小值减最小值从小到大排序（使得每次的损失最少，这个感性理解一下不难吧）。

比如说，我现在在这个 $n$ 元组中，知道了一个元素 $a_p$。那么我接下来有以下几个拓展方案：

以下是这个算法的流程。你在看的过程中可能会产生很多问号，因为直接把这个结论告诉你了，你肯定百分百看不懂。直接告诉你只是为了让你先了解这个算法的流程，看不懂没关系。

操作 $1$：将 $a_p$ 深入一层。即将 $a_1,\cdots,a_p,a_{p+1}\cdots,a_n$ 变为 $a_1,\cdots,a_p+1,a_{p+1}\cdots,a_n$。

操作 $2$：将下一个元素深入一层。即将 $a_1,\cdots,a_p,\cdots,a_n$ 变为 $a_1,\cdots,a_p,a_{p+1}+1,\cdots,a_n$。

操作 $3$：假如 $a_p=1$ 时，那么直接舍弃这个元素，选下一个元素，即将 $a_1,\cdots,1,a_{p+1},\cdots,a_n$ 变为 $a_1,\cdots,0,a_{p+1}+1,\cdots,a_n$。

接下来，我们只要证明这个方法是对的就好了。

首先，证明这个方法必然找到了前 $m$ 小的解。

- 我们发现如果想将某个元素深入一层，那就是第一个操作（感觉是废话）。

- 如果要将两个相邻的元素深入一层也是有方案的。你可能没动啥叫“将两个相邻的元素深入一层”，如下：

```
1 1 1 1 1 -> 1 2 1 1 1 -> 1 2 2 1 1
```

第 $2$ 个元素和第 $3$ 个元素均深入了一层，所以叫做“相邻的元素均深入一层”。

这个算法处理的流程是：

首先，当 $p=2$ 时，我们先将这个元素深入一层（$1$ 操作），此时 $p$ 变为 $2$。

然后 $p=2$ 会被再次找到，然后这次我们进行“将下一个元素深入一层”（$2$ 操作），此时 $p$ 变为 $3$。

然后就处理完了。

- 如果要将两个不相邻的元素深入一层也是有方案的。你可能没动啥叫“将两个不相邻的元素深入一层”，如下：

```
1 1 1 1 1 -> 1 2 1 1 1 -> 1 2 2 1 1 -> 1 2 1 2 1
```

第 $2$ 个元素和第 $4$ 个元素均深入了一层，所以叫做“不相邻的元素均深入一层”。

这个算法处理的流程是：

首先，当 $p=2$ 时，我们先将这个元素深入一层（$1$ 操作），此时 $p$ 变为 $2$。

然后 $p=2$ 会被再次找到，然后这次我们进行“将下一个元素深入一层”（$2$ 操作），此时 $p$ 变为 $3$。

当 $p=3$ 时，然后这次我们进行“删除这个元素，将下一个元素深入一层”（$3$ 操作），此时 $p=4$。

然后就处理完了。

你发现没有其他情况了。也就是说这个方法真的全处理完了，而且没有重复的！

然后到这里我再解释一下为什么第三个操作一定是在 $a_p=1$ 时执行的。

因为如果在 $a_p>1$ 时执行，那么这个操作必然可以被替换为，先以 $a_p=1$ 删除这个操作跳到下一个，然后下一个再通过 $1$ 操作深入一层。这样就重复同一个方案了。

这样每次做 $3$ 个操作，将每个元素放入优先队列里，优先队列里每次枚举到一个元素就会增加 $3$ 个元素，总共要求前 $m$ 小，所以这样复杂度就是 $O(m\log n)$，常数为 $3$。

你可能想说，这个算法太高明了！但是我是如何从题目一步一步想到这个算法的呢？

我在题解开头就曾说了这是一个构造题。所以这个东西是真的很难说是怎么想到的。所以说这个东西算是一个“求前 $k$ 小”的套路吧。

然后放个代码吧。

```cpp
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn=3e5+5;
void read(int &x){
	x=0;char ch=getchar();int f=1;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x*=f;
}
struct node{
	int x,y,v,id;
	friend bool operator < (node x,node y){return x.v>y.v;}
}p[maxn];
bool cmp(node x,node y){return x.v<y.v;}
int n,m,tot,ans,sum0,sum1,pow1[maxn];
vector<int>a[maxn],g[maxn];
priority_queue<node> q;
signed main(){
//	freopen("contain.in","r",stdin);
//	freopen("contain.out","w",stdout);
	read(n),read(m);
	for(int k,x,i=1;i<=n;i++){
		read(k);
		for(int j=1;j<=k;j++)
			read(x),a[i].pb(x);
		sort(a[i].begin(),a[i].end());
		if(k>1)p[++tot].v=a[i][1]-a[i][0],p[tot].id=i;//按次小减去最小排序选取 
		else (sum0+=a[i][0]);
	}
	sort(p+1,p+tot+1,cmp);
	for(int i=1;i<=tot;i++)
		for(int j=0;j<a[p[i].id].size();j++)
			g[i].pb(a[p[i].id][j]);//找到非只有单一元素的数列，单一放到一个 vector 里面 
	for(int i=1;i<=tot;i++)(sum1+=g[i][0]);
	ans+=(sum0+sum1);m--;
	q.push((node){1,1,(sum1-g[1][0]+g[1][1]),0});
	while(!q.empty()&&m--){
		node t=q.top();
		int x=t.x,y=t.y,v=t.v;
		q.pop();ans+=(v+sum0);
		if(y<g[x].size()-1)q.push((node){x,y+1,v-g[x][y]+g[x][y+1],0});//一号操作：将这个元素深入一层 
		if(x<tot)q.push((node){x+1,1,v-g[x+1][0]+g[x+1][1],0});//二号操作：跳到下一个元素 
		if(x<tot&&y==1)q.push((node){x+1,1,v-g[x][1]+g[x][0]-g[x+1][0]+g[x+1][1],0});//三号操作：舍弃这个元素，跳到下一个元素 
	}
	printf("%d\n",ans);
	return 0;
}

```

更新：@huangrenheluogu 大神指出了题解的不足之处。注意一开始我加入的第一个序列下标为 $1$。这是为什么呢。如果直接加入下标为 $0$ 的就会出现下面这个情况：

```
1 1 1 ----> 2 1 1 (1 号操作)---> 1 2 1 （三号操作）
1 1 1 ----> 1 2 1 (2 号操作)
```
注意这个时候方案算重了。所以我们加入下标为 $1$ 的。

那为什么别的位不会出现这个问题呢？因为别的位进入时状态就已经被更新为 $1$ 了，即选择序列第二个元素。这样就跟一开始加入下标为 $1$ 的效果相同，也就不需要特判了。

正在渲染内容...