Input
第一行是用空格隔开的二个正整数，分别给出了舞台的宽度W（1到108之间）和馅饼的个数n（1到105）。 接下来n行，每一行给出了一块馅饼的信息。由三个正整数组成，分别表示了每个馅饼落到舞台上的时刻t[i]（1到10^8秒），掉到舞台上的格子的编号p[i]（1和w之间），以及分值v[i]（1到1000之间）。游戏开始时刻为0。输入文件中同一行相邻两项之间用一个空格隔开。输入数据中可能存在两个馅饼的t[i]和p[i]都一样。
Output
一个数，表示游戏者获得的最大总得分。
Sample Input
3 4
1 2 3
5 2 3
6 3 4
1 1 5
Sample Output
12
【数据规模】
对于100%的数据，1<=w,t[i]<=10^8,1<=n<=100000。
思路
(dp_i)表示恰好接住i的最大价值
首先你发现可以转移的条件是(abs(p_i-p_j)leq 2*(t_i-t_j))
展开绝对值变成了
(2t_j-p_jleq 2t_i-p_i)
(2t_j+p_jleq 2t_i+p_i)
然后就变成了二维平面中的前缀矩形最大值统计
可以按照一个维度排序，另一个维度线段树就可以了
//Author: dream_maker
#include<bits/stdc++.h>
using namespace std;
//----------------------------------------------
//typename
typedef long long ll;
//convenient for
#define fu(a, b, c) for (int a = b; a <= c; ++a)
#define fd(a, b, c) for (int a = b; a >= c; --a)
#define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)
//inf of different typename
const int INF_of_int = 1e9;
const ll INF_of_ll = 1e18;
//fast read and write
template <typename T>
void Read(T &x) {
bool w = 1;x = 0;
char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') w = 0, c = getchar();
while (isdigit(c)) {
x = (x<<1) + (x<<3) + c -'0';
c = getchar();
}
if (!w) x = -x;
}
template <typename T>
void Write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) Write(x / 10);
putchar(x % 10 + '0');
}
//----------------------------------------------
const int N = 1e5 + 10;
struct Node {
int x, y, t, p, vl;
} p[N];
int w, n, pre[N], tot, dp[N];
bool cmp(Node a, Node b) {
return a.x < b.x;
}
#define LD (t << 1)
#define RD (t << 1 | 1)
int maxv[N << 2];
void pushup(int t) {
maxv[t] = max(maxv[LD], maxv[RD]);
}
void insert(int t, int l, int r, int pos, int vl) {
if (l == r) {
maxv[t] = vl;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) insert(LD, l, mid, pos, vl);
else insert(RD, mid + 1, r, pos, vl);
pushup(t);
}
int query(int t, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return maxv[t];
int mid = (l + r) >> 1;
if (qr <= mid) return query(LD, l, mid, ql, qr);
else if(ql > mid) return query(RD, mid + 1, r, ql, qr);
else return max(query(LD, l, mid, ql, mid), query(RD, mid + 1, r, mid + 1, qr));
}
int main() {
Read(w), Read(n);
fu(i, 1, n) {
Read(p[i].t), Read(p[i].p), Read(p[i].vl);
p[i].x = 2 * p[i].t - p[i].p;
p[i].y = 2 * p[i].t + p[i].p;
pre[i] = p[i].y;
}
sort(p + 1, p + n + 1, cmp);
sort(pre + 1, pre + n + 1);
tot = unique(pre + 1, pre + n + 1) - pre - 1;
int ans = 0;
fu(i, 1, n) {
p[i].y = lower_bound(pre + 1, pre + tot + 1, p[i].y) - pre;
dp[i] = query(1, 1, n, 1, p[i].y) + p[i].vl;
insert(1, 1, n, p[i].y, dp[i]);
ans = max(ans, dp[i]);
}
Write(ans);
return 0;
}