P9871

lsj2009 · 2023-11-19 14:41:00 · 题解

闲话

为什么都只评论不给赞啊/fn

场切了，但可能被卡常了（？

这个题和我们某场模拟赛的一个题 dp 方程长得几乎一样/jy

Problem

link：https://www.luogu.com.cn/problem/P9871。

Solution

一眼 dp，考虑设 dp 状态 f_i 为考虑前 i 天且强制第 i 天跑步的最大值，同样设 g_i=\max\limits_{j=1}^{i} f_j。

易得一个转移方程：

也就是强制第 j+1\sim i 天跑步，且第 j 天不跑。

这个 dp 方程典中典了属于是，一眼考虑使用线段树优化。

先考虑如何做到 \Theta(n\log{n})。

我们考虑线段树下标是 j 的决策点，存的东西是决策对应的值（记为 h_j），考虑当 i-1\to i 时不同决策点的代价如何变化。

首先每一个决策点 j 到 i 都比到 i-1 要多跑一天的步，所以 \forall j\in[0,i) 的 h_j\gets h_j-d。

然后这时候满足 r_p=i 的挑战 (l_p,r_p,v_p) 变得可以选择（因为随着 i 的不断右移，只要满足 l_p>j 这些挑战就始终能选择），也就是对于所有的 r_p=i,j\in[0,l_p) 的 h_j\gets h_j+v_p。

然后就得到了 f_{i}=\max\limits_{j=i-k}^{i-1} h_j，g_i=\max (g_{i-1},f_i)，而 g_i 对比转移方程恰好在 j=i+1 时取到，所以 h_{i+1}\gets h_{i+1} +g_i。

那么这就是一个 \Theta(n\log{n}) 的做法。

然后考虑如何优化到 \Theta(m\log{m})。容易发现的是，我们在转移过程中，只有 j=l_p-1 和 i=r_p 是有用的，所以我们考虑离散化，把 l_p-1,r_p 丢到离散化数组 \{t_{len}\} 里，然后就做完了。

复杂度 \Theta(m\log{m})。

Code

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=3e5+5;
namespace IO {
    char Is[(1<<21)+10],Os[(1<<21)+10];
    int Ipt,Opt;
    inline char gc() {
        if(Ipt==1<<21)
            Ipt=0;
        if(!Ipt)
            Is[fread(Is,1,1<<21,stdin)]=0;
        return Is[Ipt++];
    }
    inline void flush() {
        fwrite(Os,1,Opt,stdout);
        Opt=0;
    }
    inline void pc(char x) {
        if(Opt==1<<21)
            flush();
        Os[Opt++]=x;
    }
    inline int read() {
        int x=0;
        char ch=gc();
        while(ch<'0'||ch>'9')
            ch=gc();
        while(ch<='9'&&ch>='0')
            x=x*10+ch-'0',ch=gc();
        return x;
    }
}
using IO::read;
struct SGT {
    struct node {
        int l,r,val,tag;
    }; node tree[N<<2];
    #define ls(k) (k<<1)
    #define rs(k) (k<<1|1)
    inline void push_up(int k) {
        tree[k].val=max(tree[ls(k)].val,tree[rs(k)].val);
    }
    void build(int k,int l,int r) {
        tree[k]={l,r,0ll,0ll};
        if(l==r)
            return;
        int mid=(l+r)>>1;
        build(ls(k),l,mid);
        build(rs(k),mid+1,r);
        push_up(k);
    }
    inline void upd(int k,int val) {
        tree[k].val+=val; tree[k].tag+=val;
    }
    inline void push_down(int k) {
        int &t=tree[k].tag;
        if(t) {
            upd(ls(k),t); upd(rs(k),t);
            t=0;
        }
    }
    void update(int k,int ql,int qr,int val) {
        if(ql<=tree[k].l&&tree[k].r<=qr) {
            upd(k,val);
            return;
        }
        push_down(k);
        if(ql<=tree[ls(k)].r)
            update(ls(k),ql,qr,val);
        if(qr>=tree[rs(k)].l)
            update(rs(k),ql,qr,val);
        push_up(k);
    }
    int query(int k,int ql,int qr) {
        if(ql<=tree[k].l&&tree[k].r<=qr)
            return tree[k].val;
        push_down(k);
        int res=-INFLL;
        if(ql<=tree[ls(k)].r)
            chkmax(res,query(ls(k),ql,qr));
        if(qr>=tree[rs(k)].l)
            chkmax(res,query(rs(k),ql,qr));
        return res;
    }
}; SGT T;
int t[N],len;
inline int get_id(int x) {
    return lower_bound(t+1,t+len+1,x)-t;
}
struct seg {
    int l,r,val;
    bool operator < (const seg &tmp) const {
        return r<tmp.r;
    }
}; seg a[N];
inline void solve() {
    int n=read(),m=read(),k=read(),d=read();
    len=0;
    rep(i,1,m) {
        int r=read(),x=read(),val=read();
        a[i]={r-x,r,val};
        t[++len]=a[i].l;
        t[++len]=a[i].r;
    }
    sort(t+1,t+len+1);
    len=unique(t+1,t+len+1)-t-1;
    T.build(1,0,len-1);
    rep(i,1,m) {
        a[i].l=get_id(a[i].l); 
        a[i].r=get_id(a[i].r);
    }
    sort(a+1,a+m+1);
    int res=0,p=1;
    rep(i,1,len) {
        T.update(1,0,i-1,-d*(t[i]-t[i-1]));
        while(p<=m&&a[p].r==i)
            T.update(1,0,a[p].l,a[p].val),++p;
        chkmax(res,T.query(1,get_id(t[i]-k),i-1));
        if(i+1<len)
            T.update(1,i+1,i+1,res); 
    }
    printf("%lld\n",res);
}
//pretest at 12:44 , used time = 3.8s
signed main() {
//  freopen("run.in","r",stdin);
//  freopen("run.out","w",stdout);
    int _=read(),testcase=read();
    while(testcase--)
        solve();
    return 0;
}