Description：

从上方会不断有物品下落，每个物品有价值，每段时间回下落一格，人可以向左或向右移动一格或两格，也可以站在原地不动，问最多能收集到多少价值的物品。

$1\leqslant n\leqslant 10^5$

Solution：

如果没有移动两格，那这题就是一个新打鼹鼠。

一个非常神奇的转化是把一段时间拆成两段，每一段都可以移动一格或不移动，那么这两个其实是等价的。

还是放到坐标系上考虑，打完 $a$ 能打 $b$ 当且仅当 $2\times(b.t-a.t)\geqslant |b.x-a.x|$ ，分类讨论一下会发现其实这个等价于 $2\times(a.t-b.t)\leqslant b.x-a.x\leqslant 2\times(b.t-a.t)$ ，也就是 $2\times a.t+a.x\leqslant 2\times b.t+b.x$ 且 $2\times a.t-a.x\leqslant 2\times b.t-b.x$ ，于是这又成了一个二维偏序问题，可以排序 $+$ 树状数组。

按照坐标系的方法理解的话就是把坐标系横向拉长，于是还是一个直角。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int w,n;

#define MAXN 100010

struct point

{

	int t,p,v;

	int w1,w2;

}s[MAXN];

int b[MAXN],tot;

bool cmp_w1(point x,point y){return x.w1 < y.w1;}

typedef long long ll;

ll f[MAXN];

int lowbit(int x){return x & (-x);}

ll c[MAXN];

void add(int p,ll x){for(int i = p;i <= tot;i += lowbit(i))c[i] = max(c[i],x);return;}

ll query(int p){ll res = 0;for(int i = p;i >= 1;i -= lowbit(i))res = max(res,c[i]);return res;}

int main()

{

	scanf("%d%d",&w,&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d%d",&s[i].t,&s[i].p,&s[i].v);

		s[i].w1 = 2 * s[i].t + s[i].p;

		s[i].w2 = 2 * s[i].t - s[i].p;

		b[i] = s[i].w2;

	}

	sort(b + 1,b + 1 + n);

	tot = unique(b + 1,b + 1 + n) - b - 1;

	for(int i = 1;i <= n;++i)

	{

		s[i].w2 = lower_bound(b + 1,b + 1 + n,s[i].w2) - b;

	}

	sort(s + 1,s + 1 + n,cmp_w1);

	ll ans = 0;

	for(int i = 1;i <= n;++i)

	{

		f[i] = query(s[i].w2) + s[i].v;

		ans = max(ans,f[i]);

		add(s[i].w2,f[i]);

	}

	cout << ans << endl;

	return 0;

}