洛谷 P7302 [NOI1998] 免费的馅饼

算法分析：

首先，最基础的想法是暴力 DP 复杂度 $O(n^2)$。设 $f[i]$ 表示在前 $i$ 个馅饼中，获得第 $i$ 个馅饼的最大得分。转移方程 $f[i]=\max (f[i],f[j]+v[i])$，其中 $0<j<i$ 且 $abs(p[i],p[j])\le 2\times (t[i]-t[j])$。这个转移复杂度是 $O(n^2)$。

考虑把绝对值打开，式子就变为

$\{\begin{array}{l}p[i]-2\times t[i]\le p[j]-2\times t[j](p[i]\le p[j])\\ p[i]+2\times t[i]\ge p[j]+2\times t[j](p[i]\ge p[j])\end{array}$

那么这个式子分成两种情况，维护比较麻烦。但我们发现，如果要的那个式子满足了，另一个也会满足。所以我们让两个式子都满足。为什么呢？举个例子，假如满足了第一个式子，那么移项可以得到 $p[i]-p[j]\le 2\times t[i]-2\times t[j]$，而满足这个式子的条件是 $p[i]\le p[j]\Rightarrow p[i]-p[j]\le 0\Rightarrow t[i]\ge t[j]$。然后我们看第二个式子，$p[i]\ge p[j]$ 并且 $t[i]\ge t[j]$，显然是满足条件的。所以第一个式子满足，第二个式子也满足。

对于第一个式子，我们可以在读入的时候维护，并进行排序。这里问题就相当于变成了一个二维偏序。第二维由于数组开不下，我们需要进行离散化。

存两个关键值，$a[i].key1=a[i].p-2\times a[i].t$ 和 $a[i].key2=a[i].p+2\times a[i].t$。我们先按 $key2$ 从小到大排序，并进行离散化。

inline bool cmp2(node a,node b) { return a.key2 < b.key2; }

sort(a+1,a+n+1,cmp2);
sort(lsh+1,lsh+n+1);
unique(lsh+1,lsh+n+1)-lsh;
rep(i,1,n) a[i].key2 = lower_bound(lsh+1,lsh+n+1,a[i].key2)-lsh;

然后我们按 $key1$ 从大到小进行排序，相当于先把第一个条件给固定。对于 $key2$ 进行操作。

先来看为什么对 $key1$ 和 $key2$ 要这么排序。对于 $key1$，从大到小排序，在 $j<i$ 的时候需要满足 $a[i].key1<a[j].key1$。 $key2$ 是从小到大排序的，在 $j<i$ 的时候需要满足 $a[i].key2>a[j].key2$。所以我们发现，两个式子同时满足可以从线段树的前面转移到后面。

我们在线段树中存区间的最大值。先在线段树中求出 $1$ 到 $a[i].key2$ 的最大值，加上 $a[i].v$，然后存入线段树中 $a[i].key2$ 的位置。最后的答案就是 $t[1]$。

一个单点修改，区间查询的线段树即可。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define re register
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
inline void print(int x){
	if(x < 0) putchar('-'),x = -x;
	if(x >= 10) print(x / 10);
	putchar(x % 10 + '0');
}
const int M = 1e5+10;
struct node{
	int t,p,v;
	int key1,key2;
}a[M];
inline bool cmp1(node a,node b) { return a.key1 < b.key1; }
inline bool cmp2(node a,node b) { return a.key2 < b.key2; }
int lsh[M],tot,n,w;
#define ls (k<<1)
#define rs (k<<1|1)
int t[M<<2];
inline void pushup(int k) { t[k] = max(t[ls],t[rs]); }
inline void modify(int k,int l,int r,int x,int v){
	if(l == x && r == x){
		t[k] = v;
		return;
	}
	int mid = (l+r)>>1;
	if(x <= mid) modify(ls,l,mid,x,v);
	else modify(rs,mid+1,r,x,v);
	pushup(k);
}
inline int query(int k,int l,int r,int x,int y){
	if(x <= l && r <= y) return t[k];
	int res = 0;
	int mid = (l+r)>>1;
	if(x <= mid) res = max(res,query(ls,l,mid,x,y));
	if(y > mid)  res = max(res,query(rs,mid+1,r,x,y));
	return res;
}
signed main(){
	w = read(),n = read();
	rep(i,1,n){
		scanf("%d%d%d",&a[i].t,&a[i].p,&a[i].v);
		a[i].key1 = a[i].p - 2*a[i].t;
		lsh[i] = a[i].key2 = a[i].p + 2*a[i].t;
	}
	sort(a+1,a+n+1,cmp2);
	sort(lsh+1,lsh+n+1);
	unique(lsh+1,lsh+n+1)-lsh;
	rep(i,1,n) a[i].key2 = lower_bound(lsh+1,lsh+n+1,a[i].key2)-lsh;
	sort(a+1,a+n+1,cmp1);
	rep(i,1,n){
		int res = query(1,1,n,a[i].key2,n) + a[i].v;
		modify(1,1,n,a[i].key2,res);
	}
	printf("%d\n",t[1]);
	return 0;
}