-
分析
看到这个题就想到了二维偏序。
你们很自然地，以 \(b\) 为第一关键字降序排序，当有若干个片 \(b\) 相等时，我们发现由于 \(a < b\)，所以排到最后的片一定能把这些 \(b\) 相等的片都统计上，而前面的片能否统计是依赖于 \(b\)，所以考虑如何让后面的片更好统计，显然 \(a\) 越小越好统计，于是将 \(a\) 降序排序。
我们可以直接从前向后 DP，因为在前面的点的 \(b\) 必然不小于当前 \(b\)，所以我们在转移的时候只需要考虑转移 \(a\) 小于当前 \(b\) 的数，那么直接想到二维偏序的做法，将 DP 值存入 \(a\) 下标，用线段树快速统计 \([1,b-1]\)(即 \([1,b)\)) 下标范围内最大值转移，然后再将新的 DP 值存入当前 \(a\) 下标。
这样总时间复杂度就是 \(\mathcal{O(n \log n)}\)，可以通过本题。 -
代码
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
constexpr int MAXN(1000007);
int maxn[MAXN], lazy[MAXN], w[MAXN];
int n, tot;
inline void read(int &temp) { cin >> temp; }
struct node{
int a, b, h;
friend bool operator < (node x, node y) {
if (x.b == y.b) return x.a > y.a;
return x.b > y.b;
}
}a[MAXN];
struct SGT{
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((l + r) >> 1)
inline void pushup(int p) { maxn[p] = max(maxn[ls], maxn[rs]); }
inline void pushdown(int p) {
maxn[ls] = max(maxn[ls], lazy[p]), maxn[rs] = max(maxn[rs], lazy[p]);
lazy[ls] = max(lazy[ls], lazy[p]), lazy[rs] = max(lazy[rs], lazy[p]);
lazy[p] = 0;
}
void update(int p, int l, int r, int x, int val) {
if (l == r) return maxn[p] = max(maxn[p], val), lazy[p] = max(maxn[p], val), void();
if (lazy[p]) pushdown(p);
if (x <= mid) update(ls, l, mid, x, val);
else update(rs, mid + 1, r, x, val);
pushup(p);
}
int query(int p, int l, int r, int s, int t) {
if (s <= l && t >= r) return maxn[p];
if (lazy[p]) pushdown(p);
int res(0);
if (s <= mid) res = max(res, query(ls, l, mid, s, t));
if (t > mid) res = max(res, query(rs, mid + 1, r, s, t));
return res;
}
}Miku;
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
read(n);
for (int i(1); i <= n; ++i) read(a[i].a), read(a[i].b), read(a[i].h), w[++tot] = a[i].a, w[++tot] = a[i].b;
sort(w + 1, w + tot + 1);
tot = unique(w + 1, w + tot + 1) - w - 1;
for (int i(1); i <= n; ++i) a[i].a = lower_bound(w + 1, w + tot + 1, a[i].a) - w, a[i].b = lower_bound(w + 1, w + tot + 1, a[i].b) - w;
sort(a + 1, a + n + 1);
for (int i(1); i <= n; ++i) {
int x = Miku.query(1, 1, tot, 1, a[i].b - 1);
Miku.update(1, 1, tot, a[i].a, x + a[i].h);
}
cout << Miku.query(1, 1, tot, 1, tot) << endl;
return 0;
}