题解：P12718 [Algo Beat Contest 002 E] Excellent Game

CQ_Bab · 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;
}