上一篇 tj 因为被刷新变成棍木了，我无疑是愤怒的。

来介绍我的神奇小做法。

定义一个组合的延展为一个集合，里面包含每个背包中选入的那一个元素减去这个背包中比它小的元素中最大的那一个。

假设从当前组合出发，只允许将每一个背包中的元素降低或不变，于是这样能达到的最大组合的和，就是这个组合的和减去延展中的最小值。

显然每个背包中都选最大值的组合是所有中最大的，我们从这个出发，可以达到所有状态，所以前文假设不失正确性。

我们把这些组合的延展存进堆里，以(组合的和-延展中最小值)为关键字降序排列，每次取出堆顶，记录答案，然后要把一些新的组合的延展存进去。

其中一个显然是堆顶延展能到达的最大的组合，另一个则是钦定不能选堆顶延展中最小值，即堆顶的延展去掉最小值。

这样我们得到了一个时间 $O(nk\log n)$，空间 $O(nk)$ 的做法。

考虑怎么优化空间：每个延展和新的延展的差异其实是相当小的，于是我们考虑可持久化。

显然数组/链表/二叉堆是不好可持久化的，于是我们想到左偏树(可并堆)，这个东西只有一个 merge 操作，是好可持久化的。

于是我们写一个可持久化左偏树，一棵左偏树代表一个延展集合。在找答案的堆里，我们只用存储一个堆顶就行了。

关于时间是没有问题了，考虑空间，这个可持久化左偏树要占用 $O(n\log k)$ 的空间。考试的时候光想着尽量开大点了，考试后观察提交记录，发现开 $1.4 \times 10^7$ 差不多就行了。

本代码经过了中度卡空间。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
int T,n,k;
vector<int> vec[101000];
vector<signed> mp[101000];
signed cnt=0;
pair<signed,signed> pm[301000];
signed c[101000];
#define I(x) pm[tr[x].pos].fi
#define J(x) pm[tr[x].pos].se
#define val(x) (vec[I(x)][J(x)]-vec[I(x)][J(x)+1])
struct LeftistTree{
	signed ls,rs,d;
	signed pos;
}tr[14001000];
signed id=0;
inline int merge(int x,int y){
	if(!x||!y) return x+y;
	if(val(x)>val(y)) swap(x,y);
	int p=++id;
	tr[p]=tr[x];
	tr[p].rs=merge(tr[x].rs,y);
	if(tr[tr[p].ls].d<tr[tr[p].rs].d) swap(tr[p].ls,tr[p].rs);
	tr[p].d=tr[tr[p].rs].d+1;
	return p;
}
inline int build(signed i,signed j){
	tr[++id]={0,0,0,signed(mp[i][j])};
	return id;
}
int rt,tot;
priority_queue<pair<int,int> > pq;
pair<int,int> p[101000];
signed main(){
	cin>>n>>k;
	for(register int i=1;i<=n;i++){
		cin>>c[i];
		for(register int j=1;j<=c[i];j++){
			int x;
			cin>>x;
			vec[i].push_back(x);
			mp[i].push_back(++cnt);
			pm[cnt]={i,j-1};
		}
		vec[i].push_back(-1e18);
		sort(vec[i].begin(),vec[i].end());
		reverse(vec[i].begin(),vec[i].end());
	}
	tr[0].d=1;
	int now=0;
	for(register int i=1;i<=n;i++){
		now+=vec[i][0];
		p[i]={vec[i][0]-vec[i][1],i};
	}
	sort(p+1,p+1+n);
	for(register int i=1;i<=n;i++){
		tr[i]={signed(i*2),signed(i*2+1),0,signed(mp[p[i].se][0])};
		if(i*2>n) tr[i].ls=0;
		if(i*2+1>n) tr[i].rs=0;
	}
	for(register int i=n;i>=1;i--){
		tr[i].d=tr[tr[i].rs].d+1;
	}
	rt=1,id=n;
	cout<<now<<' ',k--;
	pq.push({now-val(rt),rt});
	for(register int i=1;i<=k;i++){
		pair<int,int> t=pq.top();
		pq.pop();
		cout<<t.fi<<' ';
		int r=merge(tr[t.se].ls,tr[t.se].rs);
		if(r) pq.push({t.fi+val(t.se)-val(r),r});
		int s=merge(r,build(I(t.se),J(t.se)+1));
		pq.push({t.fi-val(s),s});
	}
	return 0;
}