我推了一手式子，设 $f_{i,j}$ 表示 前 $i$ 项最后一项没选的为 $j$ 的匹配到的项的最大值。

转移公式：

如果 $x_i-x_{i-1}>k$ 则为 $0$。

$j\in [0,lst_i]$ 其中 $lst_i$ 表示 $i$ 第一个距离大于 $k$ 的前面的点。

其中 $j\in [0,lst_i]$。

然后发现就是区间加和加点，利用线段树维护,然后发现与奇偶性有关，所以开两个。

我感觉 $T=2$ 应该加点的时候取 min 或者 $y_i\to -y_i$ 就可以了，但是我们代码过了所有 $T=1$ 的点和两个 $T=2$ 的样例，其他全错。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=5e5+5;
const LL inf=1e15;
struct node
{
	LL l,r,lz,mx,mn; 
}t[2][N*4];
void down(node *t,LL pos)
{
	LL k=t[pos].lz;
	LL l=pos*2,r=pos*2+1;
	t[l].lz+=k,t[l].mx+=k,t[l].mn+=k;
	t[r].lz+=k,t[r].mx+=k,t[r].mn+=k;
	if(t[l].mn>inf)t[l].mn=inf;
	if(t[r].mn>inf)t[r].mn=inf;
	if(t[l].mx>inf)t[l].mx=inf;
	if(t[r].mx>inf)t[r].mx=inf;
	if(t[l].mx<0)t[l].mx=0;
	if(t[l].mn<0)t[l].mn=0;
	if(t[r].mx<0)t[r].mx=0;
	if(t[r].mn<0)t[r].mn=0;
	t[pos].lz=0;
}
void build(node *t,LL pos,LL l,LL r)
{
	t[pos].l=l,t[pos].r=r;

	t[pos].mn=inf;
	if(l==r)return;
	LL mid=(l+r)/2;
	build(t,pos*2,l,mid);
	build(t,pos*2+1,mid+1,r);
}
void upd(node *t,LL pos,LL l,LL r,LL k)
{
	if(r<t[pos].l||t[pos].r<l)return;
	if(l<=t[pos].l&&t[pos].r<=r)
	{
		t[pos].lz+=k,t[pos].mx+=k,t[pos].mn+=k;
		if(t[pos].mn>inf)t[pos].mn=inf;
		if(t[pos].mx>inf)t[pos].mx=inf;
		if(t[pos].mx<0)t[pos].mx=0;
		if(t[pos].mn<0)t[pos].mn=0;
		return;
	}
	down(t,pos);
	upd(t,pos*2,l,r,k);
	upd(t,pos*2+1,l,r,k);
	t[pos].mx=max(t[pos*2].mx,t[pos*2+1].mx);
	t[pos].mn=min(t[pos*2].mn,t[pos*2+1].mn);
}
LL query(node *t,LL pos,LL l,LL r)
{
	if(r<t[pos].l||t[pos].r<l)return 0;
	if(l<=t[pos].l&&t[pos].r<=r)return t[pos].mx;
	down(t,pos);
	return max(query(t,pos*2,l,r),query(t,pos*2+1,l,r));
}
LL query2(node *t,LL pos,LL l,LL r)
{
	if(r<t[pos].l||t[pos].r<l)return 1e18;
	if(l<=t[pos].l&&t[pos].r<=r)return t[pos].mn;
	down(t,pos);
	return min(query2(t,pos*2,l,r),query2(t,pos*2+1,l,r));
}
LL op,n,k,x[N],y[N],lst[N],sum;

int main()
{
	scanf("%lld%lld%lld",&op,&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&x[i],&y[i]);
		sum+=y[i];
	}
	for(int i=1;i<=n;i++)
	{
		lst[i]=lower_bound(x+1,x+n+1,x[i]-k)-x-1;
	}
	build(t[0],1,0,n),build(t[1],1,0,n);
	if(op==1)
	{
		for(int i=1;i<=n;i++)
		{
			if(i!=1&&x[i]-x[i-1]<=k)
			{
				upd(t[i&1],1,0,i-2,y[i]+y[i-1]);
			}
			else upd(t[i&1],1,0,i-2,-inf);
			if(3<=i&&x[i]-x[i-2]<=k)upd(t[i&1],1,i-1,i-1,query(t[(i+1)&1],1,0,lst[i-1])+y[i]-y[i-1]);
			upd(t[i&1],1,i,i,query(t[(i+1)&1],1,0,lst[i]));
		}
		printf("%lld",sum-query(t[n&1],1,0,n));
	}
	else
	{
		upd(t[0],1,0,0,-inf);
		for(int i=1;i<=n;i++)
		{
			if(i!=1&&x[i]-x[i-1]<=k)
			{
				upd(t[i&1],1,0,i-2,y[i]+y[i-1]);
			}
			else upd(t[i&1],1,0,i-2,inf);
			if(3<=i&&x[i]-x[i-2]<=k)
			{
				LL gt=query2(t[(i+1)&1],1,0,lst[i-1]);
				if(gt>=inf)gt=0;
				upd(t[i&1],1,i-1,i-1,-query2(t[i&1],1,i-1,i-1));	
				upd(t[i&1],1,i-1,i-1,gt+y[i]-y[i-1]);
			}
			upd(t[i&1],1,i,i,-query2(t[i&1],1,i,i));		
			upd(t[i&1],1,i,i,query2(t[(i+1)&1],1,0,lst[i]));		
		}
		printf("%lld",sum-query2(t[n&1],1,0,n));
	}
	return 0;
}

有老哥有什么想法可以来说一下