分析

容易发现把所有专辑变为专辑中第一个上升子序列一定不影响答案，所以我们先把这个处理出来。

随后我们可以发现，每个专辑的贡献不一定是全部段的，有可能只是后缀的一段，所以我们将所有后缀枚举出来，只记录最小的数、最大的数还有数的数量，把这些数据看成一个个区间，区间个数显然最多为数的总数即为 $\sum k_i$。

接下来就比较简单了，将所有区间按左端点升序排序，设 $f_i$ 为强制选第 $i$ 个区间的前 $i$ 个区间的最大价值，那么转移过来的 $f_j$ 的右端点必定小于第 $i$ 个区间的左端点，线段树维护即可，时间复杂度 $O(n \log n)$。

代码

#include <bits/stdc++.h>
#define ls (u<<1)
#define rs ((u<<1)|1)
#define mid ((l+r)>>1)
using namespace std;
int t,n,a[200005],cnt,m,f[200005],mx,x;
struct haa{
	int l,r,da;
	inline bool operator < (const haa &o) const{
		if(l!=o.l) return l<o.l;
		return r<o.r;
	}
};//左端点升序排序
haa c[200005];
struct ha{
	int l,r,mx;
};
ha b[800005];
inline void up(int u){
	b[u].mx=max(b[ls].mx,b[rs].mx);
}
void build(int u,int l,int r){
	b[u]=ha{l,r,0};
	if(l==r) return ;
	build(ls,l,mid);
	build(rs,mid+1,r);
}
void modify(int u,int o,int x){
	if(b[u].l>o||b[u].r<o) return ;
	if(b[u].l==b[u].r&&b[u].l==o){
		b[u].mx=max(b[u].mx,x);
		return ;
	}
	modify(ls,o,x);
	modify(rs,o,x);
	up(u);
}
int query(int u,int l,int r){
	if(b[u].l>r||b[u].r<l) return 0;
	if(b[u].l>=l&&b[u].r<=r) return b[u].mx;
	return max(query(ls,l,r),query(rs,l,r));
}//线段树
int main(){
	scanf("%d",&t);
	for(int i=1;i<=t;i++){
		scanf("%d",&n);
		cnt=0;
		for(int j=1;j<=n;j++){
			scanf("%d",&x);
			if(x>a[cnt]) a[++cnt]=x;//拆第一个上升子序列
		} 
		for(int j=1;j<=cnt;j++) c[++m]=haa{a[j],a[cnt],cnt-j+1};//拆区间
	}
	sort(c+1,c+1+m);
	build(1,0,200000);//注意，由于是维护右端点，所以要直接初始化到 200000
	for(int i=1;i<=m;i++){//DP
		f[i]=max(f[i],query(1,0,c[i].l-1)+c[i].da);
		modify(1,c[i].r,f[i]);
	} 
	for(int i=1;i<=m;i++) mx=max(mx,f[i]);
	printf("%d",mx);
	return 0;
}