自动搬运

查看原文

来自洛谷，原作者为

	CQ_Bab 行稳致远

搬运于2025-08-24 23:17:41，当前版本为作者最后更新于2025-06-21 16:18:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

首先我们猜一个结论就是将所有操作都用在一个数组上的答案一定最优，然后打个暴力发现是对的。

然后我们考虑如何动态维护前 $k$ 大的和以及支持动态修改，这不是模板吗？直接用权值线段树即可，只用支持动态插值以及删值还有求前 $k$ 大的和即可。

由于空间给的比较小，所以要离散化。

代码

细节见代码。

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
#define fire signed
#define il inline
template<class T> il void print(T x) {
	if(x<0) printf("-"),x=-x;
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
template<class T> il void in(T &x) {
    x = 0; char ch = getchar();
    int f = 1;
    while (ch < '0' || ch > '9') {if(ch=='-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    x *= f;
}
int T=1;
const int N=2e5+10;
struct node{
	int l,r;
	int cnt;
	ll sum;
}tr[N*20];
struct nodes{
	int l;
	vector<ll>v; 
}s[N];
int n,m;
ll k,q;
int idx;
ll arr[N*2];
void up(int x) {
	tr[x].sum=tr[x<<1].sum+tr[x<<1|1].sum;
	tr[x].cnt=tr[x<<1].cnt+tr[x<<1|1].cnt;
}
void modify(int u,int l,int r,int x,int k) {
	if(l==r) {
		tr[u].cnt+=k;
		tr[u].sum+=k*arr[x];
		return;
	}
	int mid=l+r>>1;
	if(mid>=x) modify(u<<1,l,mid,x,k);
	else modify(u<<1|1,mid+1,r,x,k);
	up(u);
}
ll Ans(int u,int l,int r,int k) {
	if(l==r) {
		return 1ll*arr[l]*min(k,tr[u].cnt);
	}
	int mid=l+r>>1;
	if(tr[u<<1|1].cnt>=k) return Ans(u<<1|1,mid+1,r,k);
	return Ans(u<<1,l,mid,k-tr[u<<1|1].cnt)+tr[u<<1|1].sum;
}
#define get(x) (lower_bound(arr+1,arr+1+idx,x)-arr)
void solve() {
	in(n),in(m),in(q),in(k);
	k=q*k;
	rep(i,1,n) {
		in(s[i].l);
		rep(j,1,s[i].l) {
			ll x;
			in(x);
			s[i].v.pb(x);
			arr[++idx]=x;
			arr[++idx]=x+k;
		}
	}
	sort(arr+1,arr+1+idx);
	idx=unique(arr+1,arr+1+idx)-arr-1;
	rep(i,2,n) {
		for(auto to:s[i].v) {
			int it=lower_bound(arr+1,arr+1+idx,to)-arr;
			modify(1,1,idx,it,1);
		}
	}
	for(auto to:s[1].v) modify(1,1,idx,get(to+k),1);
	ll res=Ans(1,1,idx,m);
	rep(i,2,n) {
		for(auto to:s[i-1].v) modify(1,1,idx,get(to+k),-1),modify(1,1,idx,get(to),1);
		for(auto to:s[i].v) modify(1,1,idx,get(to+k),1),modify(1,1,idx,get(to),-1);
		res=max(res,Ans(1,1,idx,m)); 
	}
	printf("%lld\n",res);
}
fire main() {
	while(T--) {
		solve();
	}
	return false;
}