CF777E题解

• 分析

  看到这个题就想到了二维偏序。
  你们很自然地，以 \(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;
}