#C240812D.「NOIP2023」天天爱打卡
网址（Website）
题目（Problem）
题目描述
小 T 同学非常热衷于跑步。为了让跑步更加有趣，他决定制作一款叫做《天天爱打卡》的软件，使得用户每天都可以进行跑步打卡。
开发完成后，小 T 同学计划进行试运行，他找了大 Y 同学来帮忙。试运行共 $n$ 天，编号为从 $1$ 到 $n$。
对大 Y 同学来说，如果某天他选择跑步打卡，那么他的能量值会减少 $d$。初始时，他的能量值是 $0$，并且试运行期间他的能量值可以是负数。
而且大 Y 不会连续跑步打卡超过 $k$ 天；即不能存在 $1\le x\le n-k$，使得他在第 $x$ 到第 $x+k$ 天均进行了跑步打卡。
小 T 同学在软件中设计了 $m$ 个挑战，第 $i$（$1\le i \le m$）个挑战可以用三个正整数 $(x_i,y_i,v_i)$ 描述，表示如果在第 $x_i$ 天时，用户已经连续跑步打卡至少 $y_i$ 天（即第 $x_i-y_i+1$ 到第 $x_i$ 天均完成了跑步打卡），那么小 T 同学就会请用户吃饭，从而使用户的能量值提高 $v_i$。
现在大 Y 想知道，在软件试运行的 $n$ 天结束后，他的能量值最高可以达到多少？
输入格式
本题的测试点包含有多组测试数据。
输入的第一行包含两个整数 $c$ 和 $t$，分别表示测试点编号和测试数据组数。对于样例，$c$ 表示该样例与测试点 $c$ 拥有相同的限制条件。
接下来，对于每组测试数据：
- 输入的第一行包含四个正整数 $n,m,k,d$，分别表示试运行的天数、挑战的个数、大 Y 单次跑步打卡的连续天数限制以及大 Y 跑步打卡减少的能量值。
- 接下来 $m$ 行，每行包含三个正整数 $x_i,y_i,v_i$，表示一次挑战。
输出格式
输出一行一个整数表示对应的答案。
样例 #1
样例输入 #1
1 1
3 2 2 1
2 2 4
3 2 3样例输出 #1
2提示
【样例解释 #1】
在第 $1,2$ 天跑步打卡，第 $3$ 天不跑步打卡，最终会获得 $(-1)+(-1)+4=2$ 的能量值。
【样例解释 #2】
该组样例满足测试点 $3$ 的条件。
【样例解释 #3】
该组样例满足测试点 $5$ 的条件。
【样例解释 #4】
该组样例满足测试点 $15$ 的条件。
【样例解释 #5】
该组样例满足测试点 $17$ 的条件。
【样例解释 #6】
该组样例满足测试点 $19$ 的条件。
【数据范围】
记 $l_i=x_i-y_i+1$，$r_i=x_i$；
对于所有测试数据，保证：$1\le t\le 10$，$1\le k\le n\le 10^9$，$1\le m\le 10^5$，$1\le l_i\le r_i\le n$，$1\le d,v_i\le 10^9$。
| 测试点编号 | $n \le$ | $m \le$ | 特殊性质 |
|---|---|---|---|
| $1, 2$ | $18$ | $10 ^ 2$ | 无 |
| $3, 4$ | $10 ^ 2$ | $10 ^ 2$ | 无 |
| $5 \sim 7$ | $10 ^ 3$ | $10 ^ 3$ | 无 |
| $8, 9$ | $10 ^ 3$ | $10 ^ 5$ | 无 |
| $10, 11$ | $10 ^ 5$ | $10 ^ 3$ | 无 |
| $12 \sim 14$ | $10 ^ 5$ | $10 ^ 5$ | 无 |
| $15, 16$ | $10 ^ 9$ | $10 ^ 5$ | A |
| $17, 18$ | $10 ^ 9$ | $10 ^ 5$ | B |
| $19 \sim 21$ | $10 ^ 9$ | $10 ^ 5$ | C |
| $22 \sim 25$ | $10 ^ 9$ | $10 ^ 5$ | 无 |
特殊性质 A：$k\le 10^2$；
特殊性质 B：$\forall 1\le i<m$，$r_i<l_{i+1}$；
特殊性质 C：$\forall 1\le i<j\le m$，$l_i<l_j$，$r_i<r_j$。
代码（Code）
#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
#define chkmax(a,b) a=max(a,b)
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 501234;
bool ST;
int tid,T;
#define mid ((l+r)>>1)
#define ls (p<<1)
#define rs (p<<1|1)
struct Segment_Tree{
struct Tr{int max,add;}tr[N<<2];
inline void pushup(Tr &T,Tr L,Tr R){T.max=max(L.max,R.max);}
inline void pushtag(int p,int v){tr[p].add+=v,tr[p].max+=v;}
inline void pushdown(int p){if(tr[p].add){int v=tr[p].add;tr[p].add=0;pushtag(ls,v),pushtag(rs,v);}}
void build(int p,int l,int r){
tr[p]={0ll,0ll};if(l==r) return;
build(ls,l,mid),build(rs,mid+1,r);
pushup(tr[p],tr[ls],tr[rs]);
}
void update(int p,int l,int r,int L,int R,int v){
if(L<=l && r<=R) return pushtag(p,v);pushdown(p);
if(L<=mid) update(ls,l,mid,L,R,v);
if(R>mid) update(rs,mid+1,r,L,R,v);
pushup(tr[p],tr[ls],tr[rs]);
}
int ask(int p,int l,int r,int L,int R){
if(L<=l && r<=R) return tr[p].max;
pushdown(p);int res = -inf;
if(L<=mid) res = max(res, ask(ls,l,mid,L,R));
if(R>mid) res = max(res, ask(rs,mid+1,r,L,R));
return res;
}
}tree;
#undef mid
#undef ls
#undef rs
struct Wolf{int l,r,v;}a[N];
int n,m,k,d;
int b[N],vn;
inline int find(int x){return lower_bound(b+1,b+vn+1,x)-b;}
void Solve(){
n=rd(),m=rd(),k=rd(),d=rd(),vn=0;
For(i,1,m){
int r=rd(),l=r-rd(),v=rd();
a[i] = {l,r,v};
b[++vn] = l, b[++vn] = r;
}
sort(b+1,b+vn+1), vn=unique(b+1,b+vn+1)-b-1;
tree.build(1,0,vn-1);
For(i,1,m) a[i].l=find(a[i].l), a[i].r=find(a[i].r);
sort(a+1,a+m+1,[&](Wolf a,Wolf b){return a.r<b.r;});
int res = 0, p = 1;
For(i,1,vn){
tree.update(1,0,vn-1,0,i-1,-d*(b[i]-b[i-1]));
while(p<=m && a[p].r==i)
tree.update(1,0,vn-1,0,a[p].l,a[p].v), p++;
if(i^1) res = max(res, tree.ask(1,0,vn-1,find(b[i]-k),i-1));
if(i+1 < vn) tree.update(1,0,vn-1,i+1,i+1,res);
}
printf("%lld\n",res);
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("run.in","r",stdin);
freopen("run.out","w",stdout);
tid=rd(),T=rd();double Tim = clock();
while(T--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
