P9871 [NOIP2023] 天天爱打卡 题解

· · 题解

记 l_i=x_i-y_i+1，r_i=x_i。

设 f_{i,j} 表示考虑到第 i 天，第 j 天不跑且第 (j+1) 天至第 i 天均跑的最大能量值。

容易得到转移方程：

\begin{aligned} & f_{i,i}=\max_{i-1-k \le s \le i-1} f_{i-1,s}\\ & f_{i,j}=f_{i-1,j}-d+\sum_{j \lt l_s \land r_s=i} v_s \ (i-k \le j \lt i) \end{aligned}

把所有 l_s-1 和 r_s 作为关键点拎出来进行离散化，因为显然只有这些点能影响最优解。设离散化数组为 t，则转移方程可以化为：

\begin{aligned} & f_{i,i}=\max_{t_{i-1}-k \le t_s\le t_{i-1}} f_{i-1,s}\\ & f_{i,j}=f_{i-1,j}-d\cdot(t_i-t_{i-1})+\sum_{t_j \lt l_s \land r_s=i} v_s\ (t_i-k \le t_j \lt t_i) \end{aligned}

注意到 f_{i,i} 的转移只需要求区间最大值，且每组 (l_s,r_s,v_s) 可以转化为区间加的形式，于是我们只需要把第一维压掉，上线段树优化，按照 r_s 的顺序利用二分转移即可。

记得开 long long，注意卡常。

#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define i128 __int128
#define endl '\n'
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define vei vector<int>
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define yes puts("yes")
#define no puts("no")
#define Yes puts("Yes")
#define No puts("No")
#define YES puts("YES")
#define NO puts("NO")
#define In(x) freopen(x".in","r",stdin)
#define Out(x) freopen(x".out","w",stdout)
#define File(x) (In(x),Out(x))
using namespace std;
static char buf[100000],*pa=buf,*pd=buf;
#define gc pa==pd&&(pd=(pa=buf)+fread(buf,1,100000,stdin),pa==pd)?EOF:*pa++
inline int read(){
    register int x(0);
    register char c(gc);
    while(c<'0'||c>'9') c=gc;
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=gc;
    return x;
}
const int N=1e5+5;
const ll inf=4e18;
vector <pii> ve[N<<1];
int n,m,k,d,x[N],y[N],v[N],w[N<<1],t[N<<1],tot,pos[N<<1];
ll val[N<<3],tag[N<<3];
void upd(int g){
    val[g]=max(val[g<<1],val[g<<1|1]);
}
void down(int g){
    if(!tag[g]) return;
    tag[g<<1]+=tag[g];
    val[g<<1]+=tag[g];
    tag[g<<1|1]+=tag[g];
    val[g<<1|1]+=tag[g];
    tag[g]=0;
}
void modify(int g,int l,int r,int x,ll k){
    if(x==l&&r==x){
        val[g]=k;
        return;
    }
    if(x<l||r<x) return;
    int m=(l+r)>>1;
    down(g);
    modify(g<<1,l,m,x,k);
    modify(g<<1|1,m+1,r,x,k);
    upd(g);
}
void add(int g,int l,int r,int x,int y,ll k){
    if(x<=l&&r<=y){
        val[g]+=k;
        tag[g]+=k;
        return;
    }
    if(y<l||r<x) return;
    int m=(l+r)>>1;
    down(g);
    add(g<<1,l,m,x,y,k);
    add(g<<1|1,m+1,r,x,y,k);
    upd(g);
}
ll ask(int g,int l,int r,int x,int y){
    if(x<=l&&r<=y) return val[g];
    if(y<l||r<x) return -inf;
    int m=(l+r)>>1;
    down(g);
    return max(ask(g<<1,l,m,x,y),ask(g<<1|1,m+1,r,x,y));
}
void solve(){
    for(int i=0;i<(N<<3);i++) val[i]=-inf,tag[i]=0;
    n=read(),m=read(),k=read(),d=read();
    for(int i=1;i<=m;i++){
        x[i]=read(),y[i]=read(),v[i]=read();
        w[i*2-1]=x[i]-y[i],w[i*2]=x[i];
    }
    sort(w+1,w+1+m*2);
    w[0]=t[1]=0,tot=1;
    for(int i=1;i<=m*2;i++) if(w[i]!=w[i-1]) t[++tot]=w[i];
    for(int i=1;i<=tot;i++) ve[i].clear();
    for(int i=1;i<=m;i++){
        int c=lb(t+1,t+1+tot,x[i])-t;
        ve[c].pb({x[i]-y[i]+1,v[i]});
    }
    modify(1,1,tot,1,0);
    for(int i=1;i<=tot;i++) pos[i]=lb(t+1,t+1+tot,t[i]-k)-t;
    for(int i=2;i<=tot;i++){
        modify(1,1,tot,i,ask(1,1,tot,pos[i-1],i-1));
        add(1,1,tot,pos[i],i-1,-1ll*d*(t[i]-t[i-1]));
        for(auto p:ve[i]){
            int r=lb(t+1,t+1+tot,p.fi)-t-1;
            if(pos[i]<=r) add(1,1,tot,pos[i],r,p.se);
        }
    }
    int l=lb(t+1,t+1+tot,t[tot]-k)-t;
    cout<<ask(1,1,tot,l,tot)<<endl;
}
signed main(){
    signed c,T=1;
    c=read(),T=read();
    while(T--) solve();
    return 0;
}