代码

#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
using Yukinoshita Yukino;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
/*
鉴定为：平衡树板子

每次操作实际上是把序列右移一位，然后在 0 位置加入个 max，没有后面的操作

所以其实进行 k 次操作就是把序列右移 k 位，全部减掉 kd，前面加入 mx,mx-d,mx-2d...

平衡树维护 ODT？？这么毒瘤的 

放弃了写平衡树（可能会暴死） 
*/
using ll=long long;
const int mxn=1e5+5;
struct op
{
	int x,y,v;
	friend bool operator <(const op &x,const op &y)
	{
		return x.x<y.x;
	}
}a[mxn];
struct node
{
	ll tp,len;
}p[mxn];
int k,d,cnt;
ll mx;
int split(int k)//[l,k-1] [k,r]
{
	int l=0,r,i,j;
	for(i=1;i<=cnt;i++)
	{
		r=l+p[i].len-1;
		if(k>=l&&k<=r)
		{
			if(k==l) return i;
			p[i].len=k-l;
			for(j=cnt+1;j>i+1;j--)
				p[j]=p[j-1];
			p[i+1]=node({p[i].tp-p[i].len*d,r-k+1});
			cnt++;
			return i+1;
		}
		l=r+1;
	}
//	assert(0);
}
void add(int d,int y,int v)//将序列先右移 d 位，在前面加入 mx,mx-d,mx-2d...，然后再把 [y,k+1] 区间+v 
{
//	cout<<d<<':'<<y<<' '<<v<<endl;
	int i;
	if(d)
	{
		split(k-d+1);
		int s=0;
//		for(i=1;i<=cnt;i++)
//			cout<<p[i].tp<<','<<p[i].len<<endl;
//		cout<<endl;
		for(i=1;i<=cnt;i++)
		{
			s+=p[i].len;
			if(s==k+1-d)
			{
				cnt=i;
				break;
			}
		}
	//	assert(i<=cnt);
		for(i=cnt+1;i>1;i--)
			p[i]=p[i-1];
		cnt++;
		p[1]=node({mx,d});
		for(i=2;i<=cnt;i++)
			p[i].tp-=1ll*d*(::d);
	}	
	else
	{
		for(i=1;i<=cnt;i++)
			p[i].tp-=1ll*d*(::d);
	}
	i=split(y);
	for(;i<=cnt;i++)
		p[i].tp+=v;
	mx=0;
	for(i=1;i<=cnt;i++)
		mx=max(mx,p[i].tp);
//	for(i=1;i<=cnt;i++)
//		cout<<p[i].tp<<' '<<p[i].len<<endl;
}
ll tp[105],tp2[105];
void add2(int d,int y,int v)//将序列先右移 d 位，在前面加入 mx,mx-d,mx-2d...，然后再把 [y,k] 区间+v 
{
	d=min(d,k+1);
	int i,j;
	for(i=0;i+d<=k;i++)
		tp2[i+d]=tp[i];
	for(i=0;i<d;i++)
		tp2[i]=mx-i*(::d);
	for(;i<=k;i++)
		tp2[i]-=1ll*d*(::d);
	for(i=y;i<=k;i++)
		tp2[i]+=v;
	for(i=0;i<=k;i++)
		tp[i]=tp2[i];
	mx=0;
	for(i=0;i<=k;i++)
		mx=max(mx,tp[i]);
}
int main()
{
	int c=read(),T=read();
	while(T--)
	{
		int n=read(),m=read(),i,j,qwq=0;
		k=read(),d=read();
		for(i=1;i<=m;i++)
		{
			a[i].x=read(),a[i].y=read(),a[i].v=read();
			if(a[i].y<=k)
				a[++qwq]=a[i];
		}
		if(k<=100)
		{
			cnt=0;
			m=qwq;
			memset(tp,128,sizeof(tp));
			tp[0]=0;
			sort(a+1,a+1+m);
			mx=0;
			for(i=1;i<=m;i++)
				add2(a[i].x-a[i-1].x,a[i].y,a[i].v);
			add2(n-a[m].x,0,0);
			printf("%lld\n",mx);
			continue;
		}
		cnt=0;
		m=qwq;
		sort(a+1,a+1+m);
		p[++cnt]=node({0,1});
		p[++cnt]=node({-1e18,k});
		mx=0;
		for(i=1;i<=m;i++)
			add(a[i].x-a[i-1].x,a[i].y,a[i].v);
		add(n-a[m].x,0,0);
		printf("%lld\n",mx);
	}
}

评测结果