这题的正常DP是 $O(n^2m)$的，如果使用单调队列可以优化到$O(nm)$，但蒟蒻太屑了，不会单调队列，于是使用线段树优化到了$O(nmlog n)$，能行吗？（或者说能不能卡过去）
还有，其他的需要使用单调队列优化的题也可以这样做吗？

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=150500,M=330;

ll f[N],ans=-1e18;
ll a[M],b[M],t[M],q[N];
int n,m,d;

struct Sn{int l,r;ll max;};
struct node{
	Sn a[N<<2];
	void push_up(int p){a[p].max=max(a[p<<1].max,a[p<<1|1].max);return ;}
	void build(int p,int l,int r){
		a[p].l=l;a[p].r=r;
		if(a[p].l==a[p].r){a[p].max=0;return ;}	
		int mid=(a[p].l+a[p].r)>>1;
		build(p<<1,l,mid);build(p<<1|1,mid+1,r);
		push_up(p);return ;
	}
	ll ask_max(int p,int l,int r){
		if(l<=a[p].l&&a[p].r<=r) return a[p].max;
		int mid=(a[p].l+a[p].r)>>1;ll re=-1e18;
		if(l<=mid) re=max(re,ask_max(p<<1,l,r));
		if(r>mid) re=max(re,ask_max(p<<1|1,l,r));
		return re;
	}
	void all_change(int p){
		if(a[p].l==a[p].r){a[p].max=q[a[p].l];return ;}
		int mid=(a[p].l+a[p].r)>>1;
		all_change(p<<1);all_change(p<<1|1);
		push_up(p);return ;
	} 
}tree;

int main(){
	scanf("%d%d%d",&n,&m,&d);
	for(int i=1;i<=m;i++) scanf("%lld%lld%lld",&a[i],&b[i],&t[i]);
	tree.build(1,1,n);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			f[j]=tree.ask_max(1,max((ll)1,j-d*(t[i]-t[i-1])),min((ll)n,j+d*(t[i]-t[i-1])))+b[i]-abs(a[i]-j);
			q[j]=f[j];
		}
		tree.all_change(1);
	}
	for(int i=1;i<=n;i++) ans=max(ans,f[i]);
	cout<<ans; 
	return 0;
}