Codeforces 960F 线段树

题意：https://blog.csdn.net/qq_39809664/article/details/79871282

思路：我们考虑LIS的状态转移，对于这个题，假设现在扫描到的边是(u, v, w),那么需要找以u为结尾的，并且值小于w的dp值。我们可以对每个节点建一颗权值线段树，询问的时候找对应节点的线段树中小于w的最大值。因为只有单点操作的过程，只要我们动态开点， 空间复杂度就是O(nlogn)的，可以开的下。

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
struct SegementTree {
	int lson, rson;
	int val;
};
SegementTree tr[maxn * 200];
int tot, root[maxn];
void pushup(int now) {
	tr[now].val = max(tr[tr[now].lson].val, tr[tr[now].rson].val);
}
void insert(int now, int l, int r, int pos, int val) {
	if(l == r) {
		tr[now].val = max(tr[now].val, val);
		return;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid) {
		if(!tr[now].lson) tr[now].lson = ++tot;
		insert(tr[now].lson, l, mid, pos, val);
	} else {
		if(!tr[now].rson) tr[now].rson = ++tot;
		insert(tr[now].rson, mid + 1, r, pos, val);
	}
	pushup(now);
}
int query(int now, int l, int r, int ql, int qr) {
	if(l >= ql && r <= qr) {
		return tr[now].val;
	}
	int mid = (l + r) >> 1, ans = 0;
	if(ql <= mid && tr[now].lson) ans = max(ans, query(tr[now].lson, l, mid, ql, qr));
	if(qr > mid && tr[now].rson) ans = max(ans, query(tr[now].rson, mid + 1, r, ql, qr));
	return ans;
}
int main() {
	int n, m, x, y, z;
	scanf("%d%d", &n, &m);
	int tmp = 0, ans = 0;
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &x, &y, &z);
		tmp = 0;
		if(root[x]) tmp = query(root[x], 0, 100000, 0, z - 1);
		if(!root[y]) root[y] = ++tot;
		insert(root[y], 0, 100000, z, tmp + 1);
	}
	for (int i = 1; i <= n; i++) {
		ans = max(ans, tr[root[i]].val);
	}
	printf("%d
", ans);
}